इस समस्या में, हमें एन रेंज [एल, आर] और क्यू प्रश्न दिए गए हैं जिनमें से प्रत्येक में एक संख्या वैल है। हमारा काम यह जांचने के लिए क्वेरीज़ को हल करने के लिए एक प्रोग्राम बनाना है कि कोई नंबर C++ में L-R की N रेंज में है या नहीं।
समस्या का विवरण
हमें [एल, आर] प्रकार की एन रेंज दी गई है जिसमें एल से आर तक पूर्णांक मान शामिल हैं, उदाहरण के लिए, रेंज [3, 6] में 3,4,5,6 शामिल हैं। प्रत्येक प्रश्न में, हमें एक वैल दिया जाता है, जिसकी उपस्थिति की जाँच की जानी है। यदि किसी एक श्रेणी में वैल मौजूद है तो प्रोग्राम सही वापस आ जाएगा अन्यथा यह झूठी वापसी करेगा।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट :रेंज [एन] ={{2, 4}, {6,7}, {9, 12}}
क्यू =3
क्वेरी ={1, 7, 10}
आउटपुट :मौजूद नहीं
वर्तमान
वर्तमान
स्पष्टीकरण
क्वेरी 1 के लिए:नंबर 1 किसी भी श्रेणी में मौजूद नहीं है।
क्वेरी 2 के लिए:संख्या 7 {6, 7} की श्रेणी में मौजूद है।
क्वेरी 1 के लिए:संख्या 10 {9, 12} की सीमा में मौजूद है।
समाधान दृष्टिकोण
हमें यह जांचने की आवश्यकता है कि क्या वैल किसी भी श्रेणी में मौजूद है, इसलिए हमें इसे सभी श्रेणियों के अनुरूप वैल की जांच करने की आवश्यकता है। इसके लिए, हम एक हैशमैप का उपयोग करेंगे। रेंज के एल और आर को अलग-अलग स्टोर करना और फिर बाइनरीसर्च एल्गोरिदम का उपयोग करके खोजना आसानी से समाधान कर देगा।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
vector<int> v;
unordered_map<int, int> mpp;
void initialiseMap(int a[][2], int n){
for (int i = 0; i < n; i++) {
v.push_back(a[i][0]);
mpp[a[i][0]] = 1;
v.push_back(a[i][1]);
mpp[a[i][1]] = 2;
}
sort(v.begin(), v.end());
}
bool isElementPresent(int val) {
int ind = lower_bound(v.begin(), v.end(), val) - v.begin();
if (v[ind] == val)
return true;
else {
if (mpp[v[ind]] == 2)
return true;
else
return false;
}
}
int main(){
int arr[][2] = {{2, 4}, {6,7}, {9, 12}};
int n = 3;
int Q = 3;
int query[] = { 1, 7, 10 };
initialiseMap(arr, n);
for(int i = 0; i < Q; i++){
cout<<"For Query "<<(i+1);
if(isElementPresent(query[i]))
cout<<": The given digit "<<query[i]<<" is present in one of the given ranges\n";
else
cout<<": The given digit "<<query[i]<<" is not present in any of the given ranges\n";
}
return 0;
} आउटपुट
For Query 1: The given digit 1 is not present in any of the given ranges For Query 2: The given digit 7 is present in one of the given ranges For Query 3: The given digit 10 is present in one of the given ranges