इस समस्या में, हमें आकार 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
समस्या को हल करने का एक अन्य दृष्टिकोण सरणी का उपयोग करना है। हम (end - start) आकार का एक बूलियन सरणी बनाएंगे। इस सरणी के प्रत्येक तत्व के लिए, हम जांचेंगे कि क्या (i+start) सरणी में मौजूद है। यदि यह मौजूद है, तो arr[i] = true मार्क करें अन्यथा arr[i] = false मार्क करें। अंत में, हम बूलियन सरणी को पार करेंगे और false मार्क किए गए सभी तत्वों को प्रिंट करेंगे।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला प्रोग्राम,
उदाहरण
#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
