এই সমস্যায়, আমাদের একটি arr[] এবং কিছু কোয়েরি দেওয়া আছে যা অ্যারেতে L থেকে R পর্যন্ত রেঞ্জ। আমাদের কাজ হল L থেকে R-এর মধ্যে সাবঅ্যারের XOR প্রিন্ট করা।
একটি উদাহরণ দিয়ে সমস্যাটি বুঝতে পারি,
ইনপুট — array = {1, 4, 5, 7, 2, 9}, L = 1, R = 5
আউটপুট —
ব্যাখ্যা — 4^5^7^2^9
- এই সমস্যাটি সমাধান করতে, আমরা একটি অ্যারে তৈরি করব নিচের অবলोकন দিয়ে,
- আমরা একাধিক বিট XOR করব, যদি ১-এর সংখ্যা বিজোড় হয়, রেজাল্ট ১ হবে অন্যথায় ০।
এখন, আমরা একটি টু-ডাইমেনশনাল অ্যারে count তৈরি করব যা ১-এর কাউন্ট স্টোর করবে। count[i][j] ভ্যালু হল i-j পজিশনের জন্য ১-এর কাউন্ট যেটি সাবঅ্যারে arr[0..j]-এ i-তম বিট পজিশনে ১-এর সংখ্যা। সাব-অ্যারে arr[L..R]-এর সব বিটের ১-এর সংখ্যা count অ্যারে দিয়ে বের করা যাবে। arr[L...R] বের করার ফর্মুলা = count[i][R] - count[i][L-1]। যদি ১-এর সংখ্যা বিজোড় হয়, তবে i-তম বিট রেজাল্টে সেট হবে। ফাইনাল রেজাল্ট পাওয়া যাবে ২-এর পাওয়ার যোগ করে যা i-তম বিট সেট বিট হলে।
উদাহরণ
আমাদের সমাধানের ইমপ্লিমেন্টেশন দেখানোর প্রোগ্রাম,
#include <bits/stdc++.h>
using namespace std;
void preProcessArray(int arr[], int n, vector<vector<int> >& cnt) {
int i, j;
for (i = 0; i < 32; i++) {
cnt[i][0] = 0;
for (j = 0; j < n; j++) {
if (j > 0) {
cnt[i][j] = cnt[i][j - 1];
}
if (arr[j] & (1 << i))
cnt[i][j]++;
}
}
}
int findXORofSubArray(int L, int R, const vector<vector<int> > count) {
int result = 0;
int noOfOnes;
int i, j;
for (i = 0; i < 32; i++) {
noOfOnes = count[i][R] - ((L > 0) ? count[i][L - 1] : 0);
if (noOfOnes & 1) {
result += (1 << i);
}
}
return result;
}
int main() {
int arr[] = {1, 4, 5, 7, 2, 9};
int n = sizeof(arr) / sizeof(arr[0]);
vector<vector<int> > count(32, vector<int>(n));
preProcessArray(arr, n, count);
int L = 1;
int R = 5;
cout << "The XOR of SubArray: " << findXORofSubArray(L, R, count);
return 0;
}
আউটপুট
The XOR of SubArray: 13
