इस समस्या में, हमें n आकार का arr[] दिया जाता है। हमारा काम है श्रेणी में एक लापता नंबर ढूंढना ।
सरणी में सबसे छोटे मान से लेकर (सबसे छोटा + n) तक के सभी मान होते हैं। श्रेणी का एक तत्व सरणी से गायब है। और हमें इस लापता मान को खोजने की जरूरत है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {4, 8, 5, 7} आउटपुट
6
समाधान दृष्टिकोण
समस्या का एक सरल समाधान यह है कि सरणी को छाँटकर लापता तत्व की खोज की जाए और फिर श्रेणी के पहले तत्व को न्यूनतम मान से शुरू किया जाए जो कि सरणी में मौजूद नहीं है लेकिन श्रेणी में मौजूद है।
यह समाधान एक अनुभवहीन दृष्टिकोण है और समस्या का समाधान O(n log n) समय जटिलता है।
कम समय में समस्या को हल करने का एक अन्य तरीका सरणी और श्रेणी के मानों के XOR का उपयोग करना है। हम श्रेणी के सभी मानों का XOR पाएंगे और सरणी के सभी मानों का 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<<"The missing value in the array is "<<findMissingNumArr(arr, n);
return 0;
} आउटपुट
The missing value in the array is 6