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

समस्या विवरण

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

उदाहरण

इनपुट

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

आउटपुट

4

हल का दृष्टिकोण

विधि 1: रैखिक खोज (O(N))

समस्या का एक सरल समाधान क्रमबद्ध सरणी को रैखिक रूप से पार करना है। और फिर इस तथ्य का उपयोग करके लापता मान की जांच करें कि arr[i] = (i + 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 << "सरणी से लापता मान है " << findMissingValArray(arr, N);
    return 0;
}

विधि 2: बाइनरी खोज (O(log N)) - इष्टतम

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

#include <iostream> 
using namespace std; 

int findMissingValArray(int arr[], int N) {
    int start = 0, end = N - 1;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (arr[mid] != mid + 1 && (mid == 0 || arr[mid - 1] == mid))
            return (mid + 1);
        if (arr[mid] != (mid + 1))
            end = mid - 1;
        else
            start = mid + 1;
    }
    return -1;
}

int main() {
    int arr[] = {1, 2, 3, 4, 6};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "सरणी से लापता मान है " << findMissingValArray(arr, N);
    return 0;
}

आउटपुट

सरणी से लापता मान है 5

जटिलता विश्लेषण

बाइनरी खोज तर्क

एक क्रमबद्ध सरणी में जिसमें 1 से N तक के तत्व और एक लापता होता है, तत्व i इंडेक्स i-1 पर होना चाहिए। यदि arr[mid] > mid+1, तो लापता तत्व बाईं ओर है। यदि arr[mid] == mid+1, तो लापता तत्व दाईं ओर है।