इस समस्या में, हमें दो पूर्णांक L और R दिए गए हैं जो एक रेंज को दर्शाते हैं। हमारा कार्य रेंज [L, R] के भीतर सभी तत्वों का XOR खोजना है।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट - L=3, R=6
व्याख्या - 3^4^5^6 =
इस समस्या को हल करने के लिए, हम R का MSB ढूंढेंगे। उत्तर का MSB R से अधिक नहीं होगा। अब, हम 0 से MSB तक बिट्स की संख्या की समता ढूंढेंगे।
अब, i-th बिट के लिए समता गणना खोजने के लिए, हम देख सकते हैं कि i-th बिट की स्थिति हर 2^i संख्या पर बदल जाएगी। वही रेंज L से R में सेट सभी i-th बिट के लिए है। ऐसा करने पर, दो मामले सामने आते हैं -
केस 1 (i != 0) - L के i-th बिट की जांच करें। यदि यह सेट है, तो L और L+2^i के बीच की संख्याओं की समता गणना जांचें। और यदि L का i-th बिट सेट है, तो L विषम है, तो गणना विषम है अन्यथा यह सम है। अब, हम R पर जाएंगे, और R-2^i और R के बीच तत्वों की संख्या की समता निर्धारित करेंगे और वही विधि अपनाएंगे।
बाकी सभी पूर्णांकों पर विचार नहीं किया जाता क्योंकि वे i-th बिट सेट के साथ पूर्णांक की सम संख्या उत्पन्न करेंगे।
केस 2 (i = 0) - यहां, हमें निम्नलिखित मामले पर विचार करना होगा -
केस 2.1 - L और R दोनों विषम हैं, 0th-बिट सेट वाले पूर्णांकों की संख्या (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 = (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
