Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में दी गई रेंज में सम संख्या में प्रकट होने वाली संख्याओं का XOR


इस समस्या में, हमें n तत्वों की एक सरणी दी गई है और कुछ क्वेरीज हैं जो सरणी में एक प्रारंभ बिंदु से अंत बिंदु तक की रेंज हैं। हमारा कार्य रेंज में सम संख्या में प्रकट होने वाले तत्वों का XOR खोजना है।

आइए एक उदाहरण से समस्या को समझते हैं,

इनपुट -

array = {1, 2, 3, 1, 1, 2, 2, 3}
querries = 2
R = 4 L = 2, R = 5
L = 2, R = 7

आउटपुट -

0 1 0

इस समस्या का समाधान काफी आसान है, हम प्रत्येक क्वेरी द्वारा दी गई रेंज में सरणी के सभी तत्वों के XOR का योग ढूंढेंगे। इसके लिए, हम prefix sum XOR का उपयोग करेंगे।

उदाहरण

हमारे समाधान के कार्यान्वयन को दिखाने वाला प्रोग्राम,

#include <bits/stdc++.h>
using namespace std;

struct que {
    int L, R, idx;
};

bool cmp(que a, que b) {
    if (a.R != b.R)
        return a.R < b.R;
    else
        return a.L < b.L;
}

int findXORSum(int BIT[], int index) {
    int xorSum = 0;
    index = index + 1;
    while (index > 0) {
        xorSum ^= BIT[index];
        index -= index & (-index);
    }
    return xorSum;
}

void updateBIT(int BIT[], int N, int index, int val) {
    index = index + 1;
    while (index <= N) {
        BIT[index] ^= val;
        index += index & (-index);
    }
}

int* createBitTree(int arr[], int N) {
    int* BIT = new int[N + 1];
    for (int i = 1; i <= N; i++)
        BIT[i] = 0;
    return BIT;
}

void findXORSolution(int arr[], int N, que queries[], int Q, int BIT[]) {
    int* prefixXOR = new int[N + 1];
    map<int, int> XORval;
    
    for (int i = 0; i < N; i++) {
        if (!XORval[arr[i]])
            XORval[arr[i]] = i;
        if (i == 0)
            prefixXOR[i] = arr[i];
        else
            prefixXOR[i] = prefixXOR[i - 1] ^ arr[i];
    }
    
    int lastOcc[1000001];
    memset(lastOcc, -1, sizeof(lastOcc));
    
    sort(queries, queries + Q, cmp);
    
    int res[Q];
    int j = 0;
    
    for (int i = 0; i < Q; i++) {
        while (j <= queries[i].R) {
            if (lastOcc[XORval[arr[j]]] != -1)
                updateBIT(BIT, N, lastOcc[XORval[arr[j]]], arr[j]);
            updateBIT(BIT, N, j, arr[j]);
            lastOcc[XORval[arr[j]]] = j;
            j++;
        }
        int allXOR = prefixXOR[queries[i].R] ^ prefixXOR[queries[i].L - 1];
        int distinctXOR = findXORSum(BIT, queries[i].R) ^ findXORSum(BIT, queries[i].L - 1);
        res[queries[i].idx] = allXOR ^ distinctXOR;
    }
    
    for (int i = 0; i < Q; i++)
        cout << res[i] << endl;
}

int main() {
    int arr[] = {1, 2, 1, 1, 2, 2, 3, 1, 3};
    int N = sizeof(arr) / sizeof(arr[0]);
    int* BIT = createBitTree(arr, N);
    
    que queries[4];
    queries[0].L = 1;
    queries[0].R = 4; queries[0].idx = 0;
    queries[1].L = 2;
    queries[1].R = 7; queries[1].idx = 1;
    queries[2].L = 0;
    queries[2].R = 3; queries[2].idx = 2;
    queries[3].L = 3;
    queries[3].R = 6; queries[3].idx = 3;
    
    int Q = sizeof(queries) / sizeof(queries[0]);
    
    cout << "Xor sum for all queries is \n";
    findXORSolution(arr, N, queries, Q, BIT);
    
    return 0;
}

आउटपुट

Xor sum for all queries is
3
2
0
2
  1. - C++ में दी गई संख्या के अंकों का उपयोग करके बनने वाली अधिकतम संख्या ज्ञात करें

    मान लीजिए हमारे पास n अंकों की एक संख्या है। हमें उस संख्या के सभी अंकों का उपयोग करके प्राप्त की जा सकने वाली अधिकतम संख्या ढूंढनी है। इसलिए यदि संख्या 339625 है, तो अधिकतम संख्या 965332 हो सकती है। समस्या से, हम देख सकते हैं कि हम आसानी से अंकों को गैर-बढ़ते क्रम में सॉर्ट कर सकते हैं, फिर उन्हें

  1. - C++ में दी गई N रेंज के सभी तत्वों को कवर करने वाली रेंज ज्ञात करें

    मान लीजिए हमारे पास n रेंज हैं जिनमें L और R हैं। हमें 0-आधारित उस रेंज का सूचकांक जांचना या ढूंढना है जो अन्य सभी n-1 रेंज को कवर करती है। यदि ऐसी कोई रेंज नहीं है, तो -1 प्रदर्शित करें। उदाहरण के लिए, यदि L = [2, 4, 3, 1], और R = [4, 6, 7, 9], तो आउटपुट 3 है। इसका मतलब है कि तीसरे सूचकांक पर रेंज

  1. - C++ में जांचें कि क्या कोई संख्या मिस्ट्री नंबर है

    यहां हम देखेंगे कि कैसे जांचें कि कोई संख्या मिस्ट्री नंबर है या नहीं। एक मिस्ट्री नंबर वह संख्या है जिसे दो संख्याओं के योग द्वारा दर्शाया जा सकता है, और वे संख्याएं एक-दूसरे की रिवर्स हैं। आइए कोड देखें ताकि बेहतर विचार मिल सके। हमें सभी जोड़ों की जांच करनी होगी और निर्णय ढूंढना होगा। उदाहरण rev