अवधारणा
n विशिष्ट पूर्णांकों के दिए गए सरणी सरणी [] के संबंध में, तत्वों को एक लापता तत्व के साथ क्रमिक रूप से आरोही क्रम में रखा गया है। हमारा काम लापता तत्व को निर्धारित करना है।
इनपुट
array[] = {1, 2, 3, 4, 5, 6, 7, 9} आउटपुट
8
इनपुट
array[] = {-4, -2, -1, 0, 1, 2} आउटपुट
-3
इनपुट
array[] = {1, 2, 3, 4} आउटपुट
-1
कोई तत्व गायब नहीं है।
विधि
सिद्धांत
-
असंगति की तलाश करें:इस सिद्धांत के अनुसार, किसी भी तत्व और उसके सूचकांक के बीच का अंतर प्रत्येक तत्व के लिए सरणी [0] होना चाहिए।
उदाहरण,
ए [] ={1, 2, 3, 4, 5} -> संगत
बी [] ={201, 202, 203, 204} -> सुसंगत
सी [] ={1, 2, 3, 5, 6} -> सी के रूप में असंगत [3] – 3! =सी [0] यानी 5 – 3! =1
-
असंगति का निर्धारण O(logN) में हर बार केवल आधे सरणी को स्कैन करने में मदद करता है।
एल्गोरिदम
-
मध्य तत्व निर्धारित करें और सत्यापित करें कि क्या यह संगत है।
-
यदि मध्य तत्व संगत है, तो सत्यापित करें कि मध्य तत्व और उसके अगले तत्व के बीच का अंतर 1 से अधिक है, अर्थात सत्यापित करें कि क्या सरणी [मध्य + 1] - सरणी [मध्य]> 1
-
यदि हाँ, तो सरणी [मध्य] + 1 अनुपलब्ध तत्व है।
-
अन्यथा, हमें मध्य तत्व से दाहिने आधे सरणी को स्कैन करना होगा और चरण -1 पर कूदना होगा।
-
-
यदि मध्य तत्व असंगत है, तो सत्यापित करें कि मध्य तत्व और उसके पिछले तत्व के बीच का अंतर 1 से अधिक है यानी सत्यापित करें कि सरणी [मध्य] - सरणी [मध्य -1]> 1
-
यदि हाँ, तो सरणी [मध्य] – 1 अनुपलब्ध तत्व है।
-
अन्यथा, हमें मध्य तत्व से बाएं आधे सरणी को स्कैन करना होगा और चरण -1 पर कूदना होगा।
-
उदाहरण
// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Shows function to return the missing element
int findMissing(int array[], int n1){
int low = 0, high = n1 - 1;
int mid1;
while (high > low){
mid1 = low + (high - low) / 2;
// Verify if middle element is consistent
if (array[mid1] - mid1 == array[0]){
// Here, no inconsistency till middle elements
// When missing element is just after
// the middle element
if (array[mid1 + 1] - array[mid1] > 1)
return array[mid1] + 1;
else{
// Go right
low = mid1 + 1;
}
}
else{
// Here inconsistency found
// When missing element is just before
// the middle element
if (array[mid1] - array[mid1 - 1] > 1)
return array[mid1] - 1;
else{
// Go left
high = mid1 - 1;
}
}
}
// Here, no missing element found
return -1;
}
// Driver code
int main(){
int array[] = { -9, -8, -6, -5, -4, -3, -2, -1, 0 };
int n1 = sizeof(array)/sizeof(array[0]);
cout <<"The Missing Element:" <<(findMissing(array, n1));
} आउटपुट
The Missing Element:-7