এই সমস্যায়, আমাদেরকে দুটি পূর্ণসংখ্যা দেওয়া হয়েছে L এবং R একটি পরিসীমা নির্দেশ করে। আমাদের কাজ হল রেঞ্জ [L, R] এর মধ্যে সমস্ত উপাদানের xor খুঁজে বের করা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
ইনপুট − L=3, R =6
ব্যাখ্যা − 3^4^5^6 =
এই সমস্যাটি সমাধান করার জন্য, আমরা R-এর MSB খুঁজে পাব। উত্তরের MSB R-এর থেকে বেশি হবে না। এখন, আমরা 0 থেকে MSB পর্যন্ত বিট সংখ্যার গণনার সমতা খুঁজে পাব।
এখন, একটি ith বিটের জন্য সমতা গণনা বের করতে, আমরা দেখতে পাচ্ছি যে প্রতি 2 তম সংখ্যায় একটি ith বিটের অবস্থা পরিবর্তিত হবে। L থেকে R রেঞ্জে সেট করা সমস্ত ith বিটের জন্য একই। এটি করার সময়, দুটি ক্ষেত্রে দেখা দেয় -
কেস 1(i !=0) − L এর ith বিট পরীক্ষা করুন। যদি এটি সেট করা থাকে, তাহলে L এবং L+2i এর মধ্যে সংখ্যার সমতা গণনা পরীক্ষা করুন। এবং যদি L-এর একটি ith বিট সেট করা হয়, তাহলে L বিজোড়, তারপর গণনাটি বিজোড়, অন্যথায় এটি জোড়। এখন, আমরা R-এ চলে যাব, এবং R-2i এবং R-এর মধ্যে কয়েকটি উপাদানের গণনার সমতা নির্ধারণ করব এবং একই পদ্ধতি অনুসরণ করব।
বাকি সমস্ত পূর্ণসংখ্যা বিবেচনায় নেওয়া হয় না কারণ তারা ith বিট সেট সহ একটি পূর্ণসংখ্যার সংখ্যাও তৈরি করবে।
কেস 2(i =0) - এখানে, আমাদের নিম্নলিখিত ক্ষেত্রে বিবেচনা করতে হবে -
কেস 2.1 − L এবং R উভয়ই বিজোড়, 0ম-বিট সেট সহ পূর্ণসংখ্যার সংখ্যা গণনা হবে (R-L)/2+1 .
কেস 2.2 − অন্যথায়, গণনাটি (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 = 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
