मान लीजिए हमारे पास पॉजिटिव इंटीजर्स का एक ऐरे arr है और क्वेरीज़ का एक ऐरे है जहां queries[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 का आकार
- 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]
