एक समस्या को हल करने के लिए जिसमें हमें एक सरणी और कुछ प्रश्न दिए जाते हैं। अब प्रत्येक प्रश्न में, हमें एक श्रेणी दी गई है। अब हमें एक ऐसी संख्या ज्ञात करने की आवश्यकता है कि x के साथ उनके xor का योग अधिकतम हो, उदाहरण के लिए
Input : A = {20, 11, 18, 2, 13}
Three queries as (L, R) pairs
1 3
3 5
2 4
Output : 2147483629
2147483645
2147483645 इस समस्या में, हम प्रत्येक स्थिति में संख्याओं में मौजूद 1 के उपसर्ग की गणना करने जा रहे हैं, क्योंकि हमने अपनी संख्या की पूर्व-गणना कर ली है, इसलिए दी गई श्रेणी में L से R तक की संख्या ज्ञात करने के लिए, हमें यह करने की आवश्यकता है आर तक अनुमानित घटाना एल तक माना जाता है।
समाधान खोजने के लिए दृष्टिकोण
इस दृष्टिकोण में, जैसा कि हमें अधिकतम योग खोजने की आवश्यकता होती है, इसलिए हमें xor के अधिकांश बिट्स को 1 के बराबर बनाने की आवश्यकता होती है; इसलिए हम जांचते हैं कि क्या किसी बिट के लिए यदि कोई 0 की संख्या से अधिक है तो हम उस बिट x को रीसेट कर देते हैं क्योंकि अब अधिकांश संख्या में वह बिट 1 के बराबर है, इसलिए जब हम उस बहुमत 1 को 0 के साथ जोड़ते हैं तो अंततः हमारे पास बहुमत होता है वह बिट 1 के बराबर है, इस प्रकार हम अपने उत्तर को अधिकतम करते हैं।
उदाहरण
उपरोक्त दृष्टिकोण के लिए C++ कोड
#include <bits/stdc++.h>
using namespace std;
#define MAX 2147483647 // 2^31 - 1
int prefix[100001][32]; // the prefix array
void prefix_bit(int A[], int n){ // taking prefix count of 1's present
for (int j = 0; j < 32; j++) // we keep 0th count as 0 and our prefix array starts with index 1
prefix[0][j] = 0;
for (int i = 1; i <= n; i++){ // making our prefix array
int a = A[i - 1]; // ith element
for (int j = 0; j < 32; j++){ // as our number is less than 2^32 so we traverse for bit 0 to 31
int x = 1 << j; // traversing in bits
if (a & x) // if this bit is one so we make the prefix count as prevcount + 1
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; // the number of elements in the range hence the number of bits
int X = MAX; // we take the max value such that all of it's bits are one
// Iterating over each bit
for (int i = 0; i < 31; i++){
int x = prefix[r][i] - prefix[l - 1][i]; // calculating the number of set bits in the given range
if (x >= numberofbits - x){ // is number of 1's is more than number of 0's
int currentbit = 1 << i; // we set the current bit to prefix for toggling that bit in x
X = X ^ currentbit; // we make toggle that bit from 1 to 0
}
}
return X; // answer
}
int main(){
int n = 5, q = 3; // number of element in our array and number of queries present
int A[] = { 210, 11, 48, 22, 133 }; // elements in our array
int L[] = { 1, 4, 2 }, R[] = { 3, 14, 4 }; // given queries
prefix_bit(A, n); // creating prefix bit array
for (int i = 0; i < q; i++)
cout << maximum_num(L[i], R[i]) << "\n";
return 0;
} आउटपुट
2147483629 2147483647 2147483629
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम पहले प्रत्येक बिट के लिए 1 के वर्तमान की उपसर्ग गणना की गणना करते हैं। अब जब हमें यह गिनती मिलती है, तो हमने अपनी सबसे बड़ी समस्या हल कर ली है जो प्रश्नों को पार कर रही थी। अभी तक, हम प्रत्येक श्रेणी को पार नहीं करने जा रहे हैं। तो हम अब हमारे उपसर्ग सरणी के माध्यम से इसकी गणना कर सकते हैं। हमारा मुख्य तर्क यह है कि जब हम ऐसी स्थिति का सामना करते हैं जहां सेट बिट संख्या रीसेट बिट्स की संख्या से अधिक होती है, तो हम सीमा में रीसेट और सेट बिट्स की संख्या की गणना करते हैं। इसलिए, हम अपने x में उस बिट को अभी रीसेट करते हैं क्योंकि हमने x को 2^31 - 1 के साथ प्रारंभ किया है, इसलिए इसके सभी बिट्स सेट हो जाएंगे, और हम x में बिट्स को टॉगल करके अपना उत्तर ढूंढते हैं।
निष्कर्ष
इस ट्यूटोरियल में, हम उस संख्या को खोजने के लिए एक समस्या का समाधान करते हैं जिसका किसी दिए गए सरणी श्रेणी के साथ एक्सओआर का योग अधिकतम है। हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (Normal) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगा होगा।