सी ++ का उपयोग करके क्रमबद्ध सरणी में एकमात्र लापता संख्या खोजें

इस समस्या में, हमें आकार N का एक एआर [] दिया जाता है जिसमें 1 से N तक के मान होते हैं, जिसमें एक मान सरणी में गायब होता है। हमारा काम है सॉर्ट किए गए एरे में एकमात्र लापता नंबर ढूंढना ।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

arr[] = {1, 2, 3, 5, 6, 7}

आउटपुट

4

समाधान दृष्टिकोण

समस्या का एक सरल समाधान क्रमबद्ध सरणी को रैखिक रूप से पार करना है। और फिर इस तथ्य का उपयोग करके लापता मान की जांच करें कि arr[i] =(i + 1)।

उदाहरण 1

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम

#include <iostream>
using namespace std;
int findMissingValArray(int arr[], int N){
   for(int i = 0; i < N; i++){
      if(arr[i] != (i+1))
         return (i+1);
   }
   return -1;
}
int main(){
   int arr[] = {1, 2, 3, 4, 6};
   int N = sizeof(arr)/sizeof(arr[0]);
   cout<<"The missing value from the array is "<<findMissingValArray(arr, N);
   return 0;
}

आउटपुट

The missing value from the array is 5

समस्या को हल करने के लिए एक अन्य दृष्टिकोण द्विआधारी खोज का उपयोग करना और मध्य में मूल्य की जांच करना है। यदि मध्य का मान मध्य+1 है और (मध्य -1) पर मान (मध्य) है तो हम बाएं उप-सरणी को पार करेंगे और इसके विपरीत।

उदाहरण 2

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम

#include <iostream>
using namespace std;
int findMissingValArray(int arr[], int N){
   int s = 0, e = N - 1;
   while (s <= e) {
      int mid = (s + e) / 2;
      if (arr[mid] != mid + 1 && arr[mid - 1] == mid)
         return (mid + 1);
      if (arr[mid] != (mid + 1))
         e = (mid - 1);
      else
         s = (mid + 1);
   }
   return -1;
}
int main(){
   int arr[] = {1, 2, 3, 4, 6};
   int N = sizeof(arr)/sizeof(arr[0]);
   cout<<"The missing value from the array is "<<findMissingValArray(arr, N);
   return 0;
}

आउटपुट

The missing value from the array is 5