इस समस्या में, हमें आकार n का एक सरणी arr[] दिया जाता है और प्रारंभ और समाप्ति सीमा को दर्शाता है। हमारा काम किसी श्रेणी के लापता तत्वों को ढूंढना है।
समस्या का विवरण - हम उस श्रेणी के तत्वों का पता लगाएंगे जो सीमा में मौजूद नहीं हैं।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {4, 6, 3, 7}, start = 3, end = 8 आउटपुट
5, 8
स्पष्टीकरण
सीमा है [3, 4, 5, 6, 7, 8]
सरणी {4, 6, 3, 7}
. हैश्रेणी के तत्व जो सरणी में मौजूद नहीं हैं वे 5, 8 हैं
समाधान दृष्टिकोण
आप इस समस्या को कई तरीकों से हल कर सकते हैं। वे हैं,
#दृष्टिकोण 1
एक सरल समाधान दृष्टिकोण सीधे सरणी में श्रेणी के सभी तत्वों की जाँच करना है। इसके लिए हम ऐरे को सॉर्ट करेंगे और फिर ऐरे में रेंज का पहला एलिमेंट ढूंढेंगे और फिर जो एलिमेंट गायब हैं उन्हें ढूंढकर प्रिंट करेंगे।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void findMissingElements(int arr[], int n, int low, int high){
sort(arr, arr + n);
int* pointerVal = lower_bound(arr, arr + n, low);
int index = pointerVal - arr;
int i = index, x = low;
while (i < n && x <= high) {
if (arr[i] != x)
cout << x << " ";
else
i++;
x++;
}
while (x <= high)
cout<<x++<<" ";
}
int main(){
int arr[] = { 4, 6, 3, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int low = 3, high = 9;
cout<<"The missing elements are ";
findMissingElements(arr, n, low, high);
return 0;
} आउटपुट
The missing elements are 5 8 9
#दृष्टिकोण 2
समस्या को हल करने के लिए एक अन्य दृष्टिकोण एक सरणी का उपयोग कर रहा है। हम आकार का एक बूलियन सरणी बनाएंगे (अंत - प्रारंभ)। इस सरणी के प्रत्येक तत्व के लिए, हम पाएंगे कि क्या (i + start) सरणी में मौजूद है। यदि यह मौजूद है, तो गिरफ्तार करें [i] =सही और गिरफ्तारी [i] =झूठा चिह्नित करें। अंत में, हम बूलियनअरे को पार करेंगे और असत्य के रूप में चिह्नित सभी तत्वों को प्रिंट करेंगे।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void findMissingElements(int arr[], int n, int start, int end){
bool boolArray[end - start + 1] = { false };
for (int i = 0; i < n; i++) {
if (start <= arr[i] && arr[i] <= end)
boolArray[arr[i] - start] = true;
}
for (int i = 0; i <= end - start; i++) {
if (boolArray[i] == false)
cout<<(start + i)<<"\t";
}
}
int main(){
int arr[] = { 4, 6, 3, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int low = 3, high = 9;
cout<<"The missing elements are ";
findMissingElements(arr, n, low, high);
return 0;
} आउटपुट
The missing elements are 5 8 9
#दृष्टिकोण 3
समस्या को हल करने का एक और तरीका हैश टेबल का उपयोग करना है। सरणी के सभी तत्वों को हैश तालिका में डालें और सम्मिलन के बाद सीमा को पार करें और उन सभी तत्वों को प्रिंट करें जो सीमा में मौजूद नहीं हैं।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void findMissingElements(int arr[], int n, int start, int end){
unordered_set<int> arrEle;
for (int i = 0; i < n; i++)
arrEle.insert(arr[i]);
for (int i = start; i <= end; i++)
if (arrEle.find(i) == arrEle.end())
cout<<i<<"\t";
}
int main(){
int arr[] = { 4, 6, 3, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int low = 3, high = 9;
cout<<"The missing elements are ";
findMissingElements(arr, n, low, high);
return 0;
} आउटपुट
The missing elements are 5 8 9