মনে করুন একটি ধনাত্মক পূর্ণসংখ্যার অ্যারে `arr` এবং একটি কুয়েরি অ্যারে `queries` আছে যেখানে `queries[i] = [Li, Ri]`, প্রতিটি কুয়েরির জন্য `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`-এর আকার
- `pre` নামক একটি অ্যারে সংজ্ঞায়িত করুন, আকার `n + 1`, এবং `pre`-কে এভাবে ফিল করুন যাতে `pre[i] := pre[i-1] XOR arr[i-1]`
- `ans` নামক আরেকটি অ্যারে সংজ্ঞায়িত করুন
- `i` = 0 থেকে কুয়েরির সংখ্যা - 1 পর্যন্ত
- `l := queries[i][0]`, `r := queries[i][1]`
- `l` এবং `r`-কে 1 বাড়ান
- `pre[r] XOR pre[l-1]`-কে `ans`-এ ইনসার্ট করুন
- `ans` রিটার্ন করুন
উদাহরণ (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]
