मान लीजिए कि हमने बिना क्रमित पूर्णांकों की एक सरणी दी है। कार्य सकारात्मक लापता संख्या को खोजने के लिए है जो दिए गए सरणी में [0 से n] की सीमा में मौजूद नहीं है। उदाहरण के लिए,
इनपुट-1 -
N = 9 arr = [0,2,5,9,1,7,4,3,6]
आउटपुट -
8
स्पष्टीकरण - दिए गए क्रमबद्ध सरणी में, '8' एकमात्र धनात्मक पूर्णांक है जो गायब है, इस प्रकार आउटपुट '8' है।
इनपुट-2 -
>N= 1 arr= [0]
आउटपुट -
1
स्पष्टीकरण - दिए गए सरणी में, '1' एकमात्र सकारात्मक पूर्णांक है जो गायब है, इस प्रकार आउटपुट '1' है।
इस समस्या को हल करने का तरीका
इस विशेष समस्या को हल करने के लिए कई दृष्टिकोण हैं। हालाँकि, हम इस समस्या को रैखिक समय O(n) और स्थिर स्थान O(1) में हल कर सकते हैं।
चूंकि हम जानते हैं कि हमारी सरणी आकार n की है और इसमें [0 से n] की सीमा में बिल्कुल तत्व शामिल हैं। इसलिए यदि हम 'n' के साथ प्रत्येक तत्व और उसके सूचकांक का XOR संचालन करते हैं, तो हम परिणामी संख्या को एक अद्वितीय संख्या के रूप में पा सकते हैं जो सरणी से गायब है।
-
[0 से n] की श्रेणी में तत्वों के साथ सरणी के N आकार का इनपुट लें।
-
एक पूर्णांक फ़ंक्शन findMissingNumber(int arr[], int size) इनपुट के रूप में एक सरणी और उसका आकार लेता है और लापता संख्या देता है।
-
आइए n . लें XOR संचालन करने के लिए एक लापता संख्या के रूप में।
-
सभी सरणी तत्वों पर पुनरावृति करें और लापता संख्या, यानी, n के संबंध में प्रत्येक सरणी तत्व और उसके अनुक्रमित के साथ XOR संचालन करें। ।
-
अब लापता नंबर लौटाएं।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
int findMissingNumber(int *arr, int size){
int missing_no= size;
for(int i=0;i<size;i++){
missing_no^= i^arr[i];
}
return missing_no;
}
int main(){
int n= 6;
int arr[n]= {0,4,2,1,6,3};
cout<<findMissingNumber(arr,n)<<endl;
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाएंगे तो यह आउटपुट को इस रूप में प्रिंट करेगा,
5
यदि हम सरणी के प्रत्येक तत्व और उसके अनुक्रमित के साथ एक्सओआर ऑपरेशन करते हैं, तो यह '5' प्रिंट करेगा जो सरणी से गायब है।