C++ में N रेंज L-R में संख्या की उपस्थिति जांचने की क्वेरी

इस समस्या में, हमें N रेंज [L, R] और Q क्वेरी दी गई हैं जिनमें प्रत्येक में एक संख्या val है। हमारा कार्य C++ में N रेंज L-R में संख्या की उपस्थिति जांचने की क्वेरी को हल करने के लिए एक प्रोग्राम बनाना है।

समस्या विवरण

हमें [L, R] प्रकार की N रेंज दी गई हैं जिनमें L से R तक पूर्णांक मान होते हैं, उदाहरण के लिए, रेंज [3, 6] में 3,4,5,6 होते हैं। प्रत्येक क्वेरी में, हमें एक val दिया जाता है, जिसकी उपस्थिति की जांच की जानी है। प्रोग्राम true वापस करेगा यदि val किसी एक रेंज में मौजूद है अन्यथा यह false वापस करेगा।

उदाहरण से समझते हैं

इनपुट: ranges[N] = {{2, 4}, {6,7}, {9, 12}}

Q = 3

Query = {1, 7, 10}

आउटपुट: Not Present, Present, Present

व्याख्या

क्वेरी 1 के लिए: संख्या 1 किसी भी रेंज में मौजूद नहीं है।

क्वेरी 2 के लिए: संख्या 7 रेंज {6, 7} में मौजूद है।

क्वेरी 3 के लिए: संख्या 10 रेंज {9, 12} में मौजूद है।

समाधान दृष्टिकोण

हमें जांचना होगा कि val किसी रेंज में मौजूद है या नहीं, इसलिए हमें val को सभी रेंज के अनुरूप जांचना होगा। इसके लिए, हम एक हैशमैप का उपयोग करेंगे। रेंज के L और R को अलग-अलग स्टोर करना और फिर बाइनरी सर्च एल्गोरिदम का उपयोग करके खोज करना समाधान को आसान बना देगा।

C++ प्रोग्राम उदाहरण

#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