ধরুন আমাদের কাছে ধনাত্মক পূর্ণসংখ্যার অ্যারে অ্যারে এবং অ্যারে কোয়েরি রয়েছে যেখানে প্রশ্নগুলি[i] =[Li, Ri], প্রতিটি প্রশ্নের জন্য i Li থেকে Ri পর্যন্ত উপাদানগুলির XOR গণনা করে (অর্থাৎ, arr[Li] XOR arr[Li+1] xor ... xor arr[Ri])। প্রদত্ত প্রশ্নের জন্য ফলাফল ধারণকারী অ্যারে খুঁজে বের করতে হবে। সুতরাং যদি ইনপুট − [1,3,4,8] এর মত হয় এবং প্রশ্নগুলি [[0,1],[1,2],[0,3],[3,3]] এর মত হয়, তাহলে ফলাফল হবে [2,7,14,8]। কারণ অ্যারের উপাদানগুলির বাইনারি উপস্থাপনা হল − 1 =0001, 3 =0011, 4 =0100 এবং 8 =1000। তারপর প্রশ্নের জন্য XOR মানগুলি হল − [0,1] =1 xor 3 =2, [1,2] =3 xor 4 =7, [0,3] =1 xor 3 xor 4 xor 8 =14 এবং [3,3] =8
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=arr এর আকার
- প্রি নামক একটি অ্যারে সংজ্ঞায়িত করুন, যার আকার n + 1, তারপর প্রি পূরণ করুন, যেমন pre[i] :=pre[i – 1] XOR arr[i – 1]
- অন্য অ্যারে উত্তর সংজ্ঞায়িত করুন
- আমি রেঞ্জ 0 থেকে প্রশ্নের সংখ্যা - 1
- l :=প্রশ্নগুলি[i, 0], r :=প্রশ্নগুলি[i, 1]
- l এবং r 1 দ্বারা বাড়ান
- প্রি[আর] XOR প্রি[l - 1], উত্তরে ঢোকান
- উত্তর ফেরত দিন
উদাহরণ(C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
int n = arr.size();
vector <int> pre(n + 1);
for(int i = 1; i <=n; i++){
pre[i] = pre[i - 1] ^ arr[i - 1];
}
vector <int> ans;
for(int i = 0; i < queries.size(); i++){
int l = queries[i][0];
int r = queries[i][1];
l++;
r++;
ans.push_back(pre[r] ^ pre[l - 1]);
}
return ans;
}
};
main(){
vector<int> v = {1,3,4,8};
vector<vector<int>> v1 = {{0,1},{1,2},{0,3},{3,3}};
Solution ob;
print_vector(ob.xorQueries(v, v1));
} ইনপুট
[1,3,4,8] [[0,1],[1,2],[0,3],[3,3]]
আউটপুট
[2,7,14,8]
