मान लीजिए हमारे पास अनसॉर्टेड पूर्णांकों की एक सरणी दी गई है। कार्य उस धनात्मक लापता संख्या को ढूंढना है जो दी गई सरणी में [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 ऑपरेशन करते हैं, तो हम परिणामी संख्या को एक अद्वितीय संख्या के रूप में ढूंढ सकते हैं जो सरणी से लापता है।
तत्वों के साथ N आकार की सरणी का इनपुट लें रेंज [0 से n] में।
एक पूर्णांक फंक्शन findMissingNumber(int arr[], int size) एक सरणी और उसके आकार को इनपुट के रूप में लेता है और लापता संख्या लौटाता है।
आइए n को XOR ऑपरेशन करने के लिए लापता संख्या के रूप में लें।
सभी सरणी तत्वों पर पुनरावृति करें और लापता संख्या के संबंध में प्रत्येक सरणी तत्व और उसके इंडेक्स के साथ XOR ऑपरेशन करें, यानी, n।
अब लापता संख्या लौटाएं।
उदाहरण
#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
यदि हम सरणी के प्रत्येक तत्व और उसके इंडेक्स के साथ XOR ऑपरेशन करते हैं, तो यह '5' प्रिंट करेगा जो सरणी से लापता है।
