এই সমস্যায়, আমাদের দুটি ইন্টিজার L এবং R দেওয়া আছে যা একটি রেঞ্জ নির্দেশ করে। আমাদের কাজ হল রেঞ্জ [L, R]-এর মধ্যে সব এলিমেন্টের XOR বের করা।
একটি উদাহরণ দিয়ে সমস্যাটি বুঝতে পারি,
ইনপুট — L=3, R=6
ব্যাখ্যা — 3^4^5^6 =
এই সমস্যাটি সমাধান করতে, আমরা R-এর MSB (Most Significant Bit) বের করব। আউটপুটের MSB R-এর চেয়ে বড় হবে না। এখন, আমরা 0 থেকে MSB পর্যন্ত বিটের সংখ্যার প্যারিটি (odd/even) বের করব।
এখন, i-তম বিটের প্যারিটি কাউন্ট বের করতে, আমরা দেখতে পাই যে i-তম বিটের স্টেট প্রতি 2^i নাম্বারে পরিবর্তন হয়। একই কথা রেঞ্জ L থেকে R-এ সেট থাকা সব i-তম বিটের জন্যও সত্য। এটি করলে দুটি কেস উদ্ভূত হয় —
কেস ১ (i != 0) — L-এর i-তম বিট চেক করুন। যদি সেট থাকে, L এবং L+2^i-এর মধ্যে নাম্বারের প্যারিটি কাউন্ট চেক করুন। এবং যদি L-এর i-তম বিট সেট থাকে, তবে L বিজোড়, তাহলে কাউন্ট বিজোড় হবে অন্যথায় জোড়। এখন, আমরা R-এ যাব, এবং R-2^i এবং R-এর মধ্যে এলিমেন্ট সংখ্যার প্যারিটি নির্ধারণ করব এবং একই পদ্ধতি ফলো করব।
বাকি সব ইন্টিজার বিবেচনা করা হয় না কারণ তারা i-তম বিট সেট থাকা ইন্টিজারের জোড় সংখ্যা জেনারেট করবে।
কেস ২ (i = 0) — এখানে, আমাদের নিচের কেসগুলো বিবেচনা করতে হবে —
কেস ২.১ — L এবং R উভয়ই বিজোড়, 0th-বিট সেট থাকা ইন্টিজারের সংখ্যা হবে (R-L)/2+1।
কেস ২.২ — অন্যথায়, কাউন্ট হবে (R-L+1)/2 রাউন্ড ডাউন করে।
উদাহরণ
আমাদের সমাধানের ইমপ্লিমেন্টেশন দেখানোর প্রোগ্রাম,
#include <iostream>
using namespace std;
int findMSB(int x) {
int ret = 0;
while ((x >> (ret + 1)) != 0)
ret++;
return ret;
}
int XOREleInRange(int L, int R) {
int max_bit = findMSB(R);
int mul = 2;
int ans = 0;
for (int i = 1; i <= max_bit; i++) {
if ((L / mul) * mul == (R / mul) * mul) {
if (((L & (1 << i)) != 0) && (R - L + 1) % 2 == 1)
ans += mul;
mul *= 2;
continue;
}
bool oddCount = 0;
if (((L & (1 << i)) != 0) && L % 2 == 1)
oddCount = (oddCount ^ 1);
if (((R & (1 << i)) != 0) && R % 2 == 0)
oddCount = (oddCount ^ 1);
if (oddCount)
ans += mul;
mul *= 2;
}
int zero_bit_cnt = (R - L + 1) / 2;
if (L % 2 == 1 && R % 2 == 1)
zero_bit_cnt++;
if (zero_bit_cnt % 2 == 1)
ans++;
return ans;
}
int main() {
int L = 1, R = 4;
cout << "The XOR of all element within the range (" << L << ", " << R << ") is: " << XOREleInRange(L, R);
return 0;
}
আউটপুট
The XOR of all element within the range (1, 4) is: 4
