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

समस्या विवरण

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

सरणी में सबसे छोटे मान से (सबसे छोटा + n) तक के सभी मान होते हैं। रेंज का एक तत्व सरणी से लापता है। और हमें इस लापता मान को खोजने की आवश्यकता है।

उदाहरण

इनपुट

arr[] = {4, 8, 5, 7}

आउटपुट

6

व्याख्या: रेंज 4 से 8 है (4, 5, 6, 7, 8)। 6 लापता है।

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

समस्या का एक सरल समाधान सरणी को क्रमबद्ध करके और फिर रेंज के पहले तत्व को न्यूनतम मान से शुरू करके खोजना है जो सरणी में मौजूद नहीं है लेकिन रेंज में मौजूद है।

यह समाधान एक भोला दृष्टिकोण है और समस्या को O(n log n) समय जटिलता में हल करेगा।

कम समय में समस्या को हल करने का एक अन्य दृष्टिकोण मानों के XOR का उपयोग करना है। हम रेंज में सभी मानों का XOR खोजेंगे और सरणी के सभी मानों का XOR भी खोजेंगे। इन दोनों मानों का XOR हमारा लापता मान होगा।

C++ कार्यान्वयन (XOR दृष्टिकोण)

#include <bits/stdc++.h> 
using namespace std; 

int findMissingNumArr(int arr[], int n) {
    int arrMin = *min_element(arr, arr + n);
    int numXor = 0;
    int rangeXor = arrMin;
    
    for (int i = 0; i < n; i++) {
        numXor ^= arr[i];
        arrMin++;
        rangeXor ^= arrMin;
    }
    
    return numXor ^ rangeXor;
}

int main() {
    int arr[] = {5, 7, 4, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "सरणी में लापता मान है " << findMissingNumArr(arr, n);
    return 0;
}

आउटपुट

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

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

• समय जटिलता: O(N)
• स्पेस जटिलता: O(1)

XOR दृष्टिकोण क्यों काम करता है

XOR के गुण: - a ^ a = 0 - a ^ 0 = a - XOR क्रमविनिमेय और साहचर्य है

रेंज XOR में सभी संख्याएं min से min+n तक होती हैं। सरणी XOR में लापता को छोड़कर सभी होती हैं। उन्हें XOR करने पर लापता संख्या रद्द हो जाती है क्योंकि अन्य सभी संख्याएं दो बार आती हैं।