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