একটি সমস্যা সমাধান করতে হবে যেখানে একটি অ্যারে এবং কিছু কোয়ারী (query) দেওয়া আছে। প্রতিটি কোয়ারীতে একটি রেঞ্জ দেওয়া আছে। এখন আমাদের এমন একটি সংখ্যা বের করতে হবে যাতে সেটির সাথে রেঞ্জের সব উপাদানের XOR যোগফল (sum of XOR) সর্বোচ্চ হয়। উদাহরণ −
ইনপুট: A = {20, 11, 18, 2, 13} তিনটি কোয়ারী (L, R) জোড়া: 1 3, 3 5, 2 4 আউটপুট: 2147483629, 2147483645, 2147483645
এই সমস্যাতেই, আমরা প্রতিটি বিট পজিশনে (bit position) ১ (ones) কতট আছে সেটির প্রিফিক্স কাউন্ট (prefix count) নিব। যেহেতু প্রিক্যালকুলেটেড (precalculated) আছে, তাই L থেকে R রেঞ্জে ১-এর সংখ্যা বের করতে prefix[R] - prefix[L-1] করলেই হবে।
এই পদ্ধতিতে, যেহেতু আমাদের সর্বোচ্চ যোগফল (maximum sum) বের করতে হচ্ছে, তাই আমরা XOR-এর অধিকাংশ বিট ১ রাখতে চাই। তাই প্রতিটি বিট পজিশনে চেক করব: যদি ১-এর সংখ্যা ০-এর সংখ্যা থেকে বেশি হয়, তবে X-র সেটি বিটকে ০ (reset) করব। কারণ অধিকাংশ সংখ্যা সেটি বিটে ১ রাখলে, সেগুলো ০ দিয়ে XOR করলে অধিকাংশ ফলাফলে সেটি বিট ১ থাকবে। এভাবেই আমরা উত্তর সর্বোচ্চ করব।
উপরোক্ত পদ্ধতির C++ কোড
#include <bits/stdc++.h> using namespace std; #define MAX 2147483647 // 2^31 - 1 int prefix[100001][32]; // প্রিফিক্স অ্যারে void prefix_bit(int A[], int n){ // প্রতিটি বিটে ১-এর প্রিফিক্স কাউন্ট for (int j = 0; j < 32; j++) prefix[0][j] = 0; // ০-ই ইনডেক্স ০ for (int i = 1; i <= n; i++){ // প্রিফিক্স অ্যারে তৈরি int a = A[i - 1]; // i-তম উপাদান for (int j = 0; j < 32; j++){ // ২^৩২ চেয়ে ছোট সংখ্যা, বিট ০-৩১ int x = 1 << j; // বিটে ট্রাভার্স if (a & x) // বিট ১ হলে প্রিফিক্স কাউন্ট + ১ 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; // রেঞ্জে এলিমেন্ট সংখ্যা = বিট সংখ্যা int X = MAX; // সর্বোচ্চ মান যাতে সব বিট ১ // প্রতিটি বিটের ওপর ইটারেট for (int i = 0; i < 31; i++){ int x = prefix[r][i] - prefix[l - 1][i]; // রেঞ্জে সেট বিটের সংখ্যা if (x >= numberofbits - x){ // ১ বেশি হলে ০-এর চেয়ে int currentbit = 1 << i; // করেন্ট বিট টগল করার জন্য X = X ^ currentbit; // ১ থেকে ০-এ টগল } } return X; // উত্তর } int main(){ int n = 5, q = 3; // অ্যারে সাইজ ও কোয়ারী সংখ্যা int A[] = { 210, 11, 48, 22, 133 }; // অ্যারে এলিমেন্ট int L[] = { 1, 4, 2 }, R[] = { 3, 14, 4 }; // কোয়ারী prefix_bit(A, n); // প্রিফিক্স বিট অ্যারে তৈরি for (int i = 0; i < q; i++) cout << maximum_num(L[i], R[i]) << "\n"; return 0; }
2147483629 2147483647 2147483629
এই পদ্ধতিতে, আমরা প্রথমে প্রতিটি বিটের ১-এর প্রিফিক্স কাউন্ট বের করি। এখন এই কাউন্ট পাওয়ায় আমরা সবচেয়ে বড় সমস্যা সমাধান করেছি যা ছিল প্রতিটি কোয়ারীর জন্য রেঞ্জ ট্রাভার্স করা। এখন প্রিফিক্স অ্যারে দিয়ে O(1)-এ বের করা যায়। আমাদের মূল লজিক: রেঞ্জে সেট (set) এবং রিসেট (reset) বিটের সংখ্যা বের করি। যেখানে সেট বিট বেশি, সেখানে X-র সেটি বিটকে ০ করি। যেহেতু X কে 2^31 - 1 দিয়ে ইনিশিয়ালাইজ করা হয়েছে (সব বিট ১), তাই বিটগুলো টগল (toggle) করে উত্তর বের করি।
এই টিউটোরিয়ালে আমরা অ্যারে রেঞ্জের সাথে XOR যোগফল সর্বোচ্চ হবে এমন সংখ্যা বের করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার C++ প্রোগ্রাম ও সম্পূর্ণ পদ্ধতি দেখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়। আশা করি আপনি এই টিউটোরিয়ালটি সহায়ক পাবেন।
