প্রদত্ত পরিসরে উপস্থিত সমস্ত সাবয়ারের XOR গণনা করতে এবং এটি মুদ্রণ করতে। যেমন
Input : arr[] = { 4, 1, 2, 3, 5 }, Q = 3
Queries
q1 = { 1, 2 }
q2 = { 2, 4 }
q3 = { 1, 4 }
Output : 0
2
0
Explanation : As the given problem states that we need to find XOR of all the subarrays present in the given range so as for query 2 the subarrays are :
{1}, {2}, {3}, {1, 2}, {2, 3}, (1, 2, 3}
So as you can see the number of occurrences of elements are :
1 is present 3 times
2 is present 4 times
3 is present 3 times
Now as we know the property of XOR is that the numbers that are present an even number of times get canceled out so out 2 got canceled out and just the XOR of 3 and 1 remained and that was our answer. এই সমস্যায় যে প্যাটার্ন তৈরি হচ্ছে তা আমাদের পর্যবেক্ষণ করতে হবে, এবং তারপর সেই অনুযায়ী আমাদের এটি বাস্তবায়ন করতে হবে।
সমাধান খোঁজার পদ্ধতি
এই সমস্যাটিতে, আমরা সমস্যাটির মধ্যে বিদ্যমান প্যাটার্নগুলি খুঁজে বের করার চেষ্টা করছি। কখন. যখন আমরা সেই প্যাটার্নটি দেখি, তখন আমরা সেই অনুযায়ী তা বাস্তবায়ন করি এবং ফলাফল পরীক্ষা করি।
উদাহরণ
উপরের পদ্ধতির জন্য C++ কোড
#include <bits/stdc++.h>
using namespace std;
void ansQueries(int prefeven[], int prefodd[], int l, int r){
if ((r - l + 1) % 2 == 0) // if number of element present in the range is even
cout << "0";
else{
if (l % 2 == 0) // if l is even
cout << (prefeven[r] ^ prefeven[l - 1]) << "\n";
else // if l is odd
cout << (prefodd[r] ^ prefodd[l - 1]) << "\n";
}
}
int main(){
int arr[] = {4, 1, 2, 3, 5};
int n = sizeof(arr) / sizeof(int); // size of our array
int l[] = {1, 2, 1}; // given queries' left index
int r[] = {2, 4, 4}; // given queries' right index
int q = sizeof(l) / sizeof(int); // number of queries asked
int prefodd[n] = {0}, prefeven[n] = {0}; // different prefix xor for even and odd indices
for (int i = 1; i <= n; i++){
if ((i) % 2 == 0){ // if i is even then we change prefeven
prefeven[i] = arr[i - 1] ^ prefeven[i - 1];
prefodd[i] = prefodd[i - 1];
}else{
prefeven[i] = prefeven[i - 1];
prefodd[i] = prefodd[i - 1] ^ arr[i - 1];
}
}
for (int i = 0; i < q; i++){
ansQueries(prefeven, prefodd, l[i], r[i]);
}
return 0;
} আউটপুট
02 0
উপরের কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা প্রথমে লক্ষ্য করি যে যদি আমাদের পরিসরের আকার জোড় হয় তবে আমাদের উত্তর হবে শূন্য কারণ প্রতিটি সংখ্যা এমনও সময়ে উপস্থিত হয় যখন আমরা সমস্ত সাবয়ারে প্রিন্ট করি তাই তাদের XOR গ্রহণ করলে উত্তরটি এখন আমাদের পরবর্তী অংশের জন্য 0 হবে। যেখানে পরিসরের আকার বিজোড় এই ক্ষেত্রে যে সংখ্যাটি বিজোড় বার দেখা যাচ্ছে তা প্রদত্ত পরিসরে জোড় অবস্থানে রয়েছে এবং আমাদের উত্তরটি কেবলমাত্র প্রদত্ত পরিসরে জোড় অবস্থানে উপস্থিত সংখ্যার XORs হবে আমরা দুটি উপসর্গ বজায় রাখি যে অ্যারেগুলি বিকল্প অবস্থানের XOR ধারণ করে কারণ আমাদের prefeven-এ সমস্ত জোড় সূচকের XOR থাকে এবং prefodd-এ সমস্ত বিজোড় সূচকের XOR থাকে এখন যখন আমরা একটি প্রশ্নের সমাধান করি তখন আমাদের কেবল আমাদের l জোড় বা বিজোড় কিনা তা পরীক্ষা করতে হবে এবং সেই অনুযায়ী আমাদের উত্তর দিতে হবে .
উপসংহার
এই টিউটোরিয়ালে, আমরা সমস্ত সাবয়ারের XOR-এর XOR-এর প্রশ্নের সমাধান করার জন্য একটি সমস্যার সমাধান করি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷
