একটি সমস্যা সমাধানের জন্য যেখানে আমাদের একটি অ্যারে এবং কিছু প্রশ্ন দেওয়া হয়। এখন প্রতিটি প্রশ্নে, আমাদের একটি পরিসর দেওয়া হয়। এখন আমাদের এমন একটি সংখ্যা খুঁজে বের করতে হবে যাতে x এর সাথে তাদের xor-এর যোগফল সর্বাধিক করা হয়, উদাহরণস্বরূপ
Input : A = {20, 11, 18, 2, 13}
Three queries as (L, R) pairs
1 3
3 5
2 4
Output : 2147483629
2147483645
2147483645 এই সমস্যায়, আমরা এখন প্রতিটি অবস্থানে সংখ্যার মধ্যে 1 এর বর্তমানের একটি উপসর্গ গণনা করতে যাচ্ছি যেহেতু আমরা আমাদের সংখ্যাগুলির পূর্বনির্ধারণ করেছি, তাই L থেকে R পর্যন্ত প্রদত্ত পরিসরের সংখ্যাগুলি খুঁজে বের করার জন্য আমাদের প্রয়োজন অনুমান করা R পর্যন্ত বিয়োগ করুন এবং অনুমান করা পর্যন্ত L.
সমাধান খোঁজার পদ্ধতি
এই পদ্ধতিতে, যেহেতু আমাদের সর্বাধিক যোগফল খুঁজে বের করতে হবে, তাই আমাদের xor-এর সংখ্যাগরিষ্ঠ বিটকে 1-এর সমান করতে হবে; তাই আমরা পরীক্ষা করি যে কোনো বিটের জন্য যদি একটি 0 এর সংখ্যার চেয়ে বেশি হয় তাই আমরা x-এর সেই বিটটিকে পুনরায় সেট করি যেহেতু এখন সংখ্যার সংখ্যাগরিষ্ঠ সংখ্যার সেই বিটটি 1 এর সমান তাই যখন আমরা সেই সংখ্যাগরিষ্ঠ 1 এর সাথে 0 এর সাথে যুক্ত করি তখন শেষ পর্যন্ত আমাদের সংখ্যাগরিষ্ঠতা থাকে যে বিট 1 এর সমান এইভাবে আমরা আমাদের উত্তরকে সর্বোচ্চ করতে পারি।
উদাহরণ
উপরের পদ্ধতির জন্য C++ কোড
#include <bits/stdc++.h>
using namespace std;
#define MAX 2147483647 // 2^31 - 1
int prefix[100001][32]; // the prefix array
void prefix_bit(int A[], int n){ // taking prefix count of 1's present
for (int j = 0; j < 32; j++) // we keep 0th count as 0 and our prefix array starts with index 1
prefix[0][j] = 0;
for (int i = 1; i <= n; i++){ // making our prefix array
int a = A[i - 1]; // ith element
for (int j = 0; j < 32; j++){ // as our number is less than 2^32 so we traverse for bit 0 to 31
int x = 1 << j; // traversing in bits
if (a & x) // if this bit is one so we make the prefix count as prevcount + 1
prefix[i][j] = 1 + prefix[i - 1][j];
else
prefix[i][j] = prefix[i - 1][j];
}
}
}
int maximum_num(int l, int r){
int numberofbits = r - l + 1; // the number of elements in the range hence the number of bits
int X = MAX; // we take the max value such that all of it's bits are one
// Iterating over each bit
for (int i = 0; i < 31; i++){
int x = prefix[r][i] - prefix[l - 1][i]; // calculating the number of set bits in the given range
if (x >= numberofbits - x){ // is number of 1's is more than number of 0's
int currentbit = 1 << i; // we set the current bit to prefix for toggling that bit in x
X = X ^ currentbit; // we make toggle that bit from 1 to 0
}
}
return X; // answer
}
int main(){
int n = 5, q = 3; // number of element in our array and number of queries present
int A[] = { 210, 11, 48, 22, 133 }; // elements in our array
int L[] = { 1, 4, 2 }, R[] = { 3, 14, 4 }; // given queries
prefix_bit(A, n); // creating prefix bit array
for (int i = 0; i < q; i++)
cout << maximum_num(L[i], R[i]) << "\n";
return 0;
} আউটপুট
2147483629 2147483647 2147483629
উপরের কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা প্রথমে প্রতিটি বিটের জন্য 1 এর বর্তমান উপসর্গ গণনা করি। এখন যখন আমরা এই গণনাটি পেয়েছি, তখন আমরা আমাদের সবচেয়ে বড় সমস্যাটি সমাধান করেছি যা প্রশ্নগুলিকে অতিক্রম করছিল। এখন পর্যন্ত, আমরা প্রতিটি রেঞ্জের মধ্য দিয়ে যেতে যাচ্ছি না। তাই আমরা এখন আমাদের উপসর্গ অ্যারের মাধ্যমে যে গণনা করতে পারেন. আমাদের প্রধান যুক্তি হল যে আমরা রিসেট এবং সেট বিটের সংখ্যা গণনা করি যখন আমরা এমন একটি অবস্থানের সম্মুখীন হই যেখানে সেট বিট সংখ্যা রিসেট বিটের সংখ্যার চেয়ে বেশি। তাই, আমরা এখন আমাদের x-এ সেই বিটটিকে রিসেট করি যেহেতু আমরা 2^31 - 1 দিয়ে x শুরু করেছি তাই এর সমস্ত বিট সেট হয়ে যাবে, এবং আমরা বিটগুলিকে x-এ টগল করে আমাদের উত্তর খুঁজে পাই।
উপসংহার
এই টিউটোরিয়ালে, আমরা একটি সমস্যার সমাধান করি সেই নম্বরটি খুঁজে বের করার জন্য যার সমষ্টি একটি প্রদত্ত অ্যারে রেঞ্জ সহ XOR-এর সর্বোচ্চ। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (স্বাভাবিক) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷
