इस लेख में, हमें पूर्णांकों की एक सरणी दी गई है। हमें बिटवाइज़ या दी गई श्रेणी में मौजूद सभी नंबरों को खोजने का काम सौंपा गया है, उदाहरण के लिए,
Input: arr[] = {1, 3, 1, 2, 3, 4}, q[] = {{0, 1}, {3, 5}}
Output:
3
7
1 OR 3 = 3
2 OR 3 OR 4 = 7
Input: arr[] = {1, 2, 3, 4, 5}, q[] = {{0, 4}, {1, 3}}
Output:
7
7 दी गई समस्या में, हम इसे एक क्रूर बल दृष्टिकोण के साथ देखेंगे और फिर जांच करेंगे कि यह उच्च बाधाओं के लिए काम कर सकता है या नहीं। यदि नहीं, तो हम उच्च बाधाओं के लिए भी काम करने के अपने दृष्टिकोण को अनुकूलित करेंगे।
क्रूर फ़ोर्स अप्रोच
इस दृष्टिकोण में, हम बस प्रत्येक श्रेणी के माध्यम से पार करने जा रहे हैं और उस सीमा में सभी संख्याओं की बिटवाइज या गणना करते हैं और अपना उत्तर प्रिंट करते हैं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = { 7, 5, 3, 5, 2, 3 };
int n = sizeof(arr) / sizeof(int); // size of our array
int queries[][2] = { { 1, 3 }, { 4, 5 } }; // given queries
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for(int i = 0; i < q; i++) { // traversing through all the queries
long ans = 0;
for(int j = queries[i][0]; j <= queries[i][1]; j++) // traversing through the range
ans |= arr[j]; // calculating the answer
cout << ans << "\n";
}
return 0;
} आउटपुट
7 3
इस दृष्टिकोण में ओ (एन * क्यू) की समय जटिलता है जहां एन हमारे सरणी का आकार है और क्यू अब प्रश्नों की संख्या है जैसा कि आप देख सकते हैं, यह जटिलता उच्च बाधाओं के लिए काम नहीं करेगी, इसलिए अब हम अपने दृष्टिकोण को अनुकूलित करेंगे जैसे कि यह उच्च बाधाओं के लिए भी काम करता है।
कुशल दृष्टिकोण
इस दृष्टिकोण में, हम उपसर्ग बिट्स गिनती की गणना करेंगे, और फिर हम जांच करेंगे कि किसी भी संख्या में एक विशेष बिट सेट है या नहीं। यदि हाँ, तो हम इस बिट को उत्तर में रखते हैं; अन्यथा, हम इसे थोड़ा छोड़ देते हैं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define bitt 32
#define MAX (int)10e5
int prefixbits[bitt][MAX];
void bitcount(int *arr, int n) { // making prefix counts
for (int j = 31; j >= 0; j--) {
prefixbits[j][0] = ((arr[0] >> j) & 1);
for (int i = 1; i < n; i++) {
prefixbits[j][i] = arr[i] & (1LL << j);
prefixbits[j][i] += prefixbits[j][i - 1];
}
}
return;
}
int check(int l, int r) { // calculating the answer
long ans = 0; // to avoid overflow we are taking ans as long
for (int i = 0; i < 32; i++) {
int x;
if (l == 0)
x = prefixbits[i][r];
else
x = prefixbits[i][r] - prefixbits[i][l - 1];
if (x != 0)
ans = (ans | (1LL << i));
}
return ans;
}
int main() {
int arr[] = {7, 5, 3, 5, 2, 3};
int n = sizeof(arr) / sizeof(int); // size of our array
bitcount(arr, n);
int queries[][2] = {{1, 3}, {4, 5}}; // given queries
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for (int i = 0; i < q; i++) {
cout << check(queries[i][0], queries[i][1]) << "\n";
}
return 0;
} आउटपुट
7 3
इस दृष्टिकोण की समय जटिलता O(N) . है , जहां एन हमारे सरणी का आकार है ताकि यह दृष्टिकोण उच्च बाधाओं के लिए काम कर सके।
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम उपसर्ग बिट्स की गणना कर रहे हैं और इसे संग्रहीत कर रहे हैं। अब हम एक क्वेरी की गणना करते हैं जो हम उस उपसर्ग गणना के माध्यम से जाते हैं और एल -1 की बिट गणना को हटा देते हैं जैसे कि हमारे पास [एल, आर] श्रेणी में संख्याओं की संख्याएं होती हैं, जैसा कि हम उन्हें जानते हैं यदि बिट किसी भी संख्या में सेट है इसलिए यदि आप इसे बिटवाइज़ लेते हैं या किसी अन्य नंबर के साथ बिट सेट रहेगा तो बिटवाइज़ की इस संपत्ति का उपयोग करके या हम जांचते हैं कि क्या बिट काउंट शून्य नहीं है, जिसका अर्थ है कि सेट बिट वाला नंबर रेंज में मौजूद है, इसलिए हम उस बिट को सेट करते हैं उत्तर दें और लूप के माध्यम से जारी रखें और अंत में उत्तर को प्रिंट करें।
निष्कर्ष
यह आलेख दिए गए सरणी के बिटवाइज़ या इंडेक्स रेंज [एल, आर] के लिए क्वेरीज़ की गणना करने के लिए एक समस्या हल करता है। हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (सामान्य और कुशल) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह लेख मददगार लगा होगा।
