C++-এ দেওয়া রেঞ্জে জোড় সংখ্যক বার আসা নাম্বাদের XOR

এই সমস্যায়, আমাদের n উপাদানের একটি অ্যারে দেওয়া আছে এবং কিছু কোয়েরি আছে যা অ্যারেতে একটি স্টার্ট পয়েন্ট থেকে এন্ড পয়েন্ট পর্যন্ত রেঞ্জ। আমাদের কাজ হল রেঞ্জে জোড় সংখ্যক বার আসা উপাদানগুলোর XOR বের করা।

একটি উদাহরণ দিয়ে সমস্যাটি বুঝতে পারি,

ইনপুট —

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

আউটপুট —

0
1
0

এই সমস্যাটির সমাধান খুব সহজ, আমরা প্রতিটি কোয়েরি দিয়ে রেঞ্জের মধ্যে অ্যারের সব এলিমেন্টের XOR সম বের করব। এর জন্য আমরা প্রিফিক্স সাম 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