इस लेख में, हमें पूर्णांकों का एक एरे दिया गया है। हमें दिए गए रेंज में मौजूद सभी संख्याओं का बिटवाइज OR खोजने का काम सौंपा गया है, उदाहरण के लिए:
इनपुट: arr[] = {1, 3, 1, 2, 3, 4}, q[] = {{0, 1}, {3, 5}}
आउटपुट: 3 7
1 OR 3 = 3
2 OR 3 OR 4 = 7
इनपुट: arr[] = {1, 2, 3, 4, 5}, q[] = {{0, 4}, {1, 3}}
आउटपुट: 7 7
दिए गए समस्या में, हम इसे ब्रूट फोर्स दृष्टिकोण के साथ हल करेंगे और फिर जांचेंगे कि क्या यह उच्च प्रतिबंधों के लिए काम कर सकता है या नहीं। यदि नहीं, तो हम अपने दृष्टिकोण को अनुकूलित करेंगे ताकि यह उच्च प्रतिबंधों के लिए भी काम करे।
ब्रूट फोर्स दृष्टिकोण
इस दृष्टिकोण में, हम केवल प्रत्येक रेंज के माध्यम से ट्रैवर्स करेंगे और उस रेंज में सभी संख्याओं का बिटवाइज OR निकालेंगे और अपना उत्तर प्रिंट करेंगे।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {7, 5, 3, 5, 2, 3};
int n = sizeof(arr) / sizeof(int); // हमारे एरे का आकार
int queries[][2] = {{1, 3}, {4, 5}}; // दी गई क्वेरी
int q = sizeof(queries) / sizeof(queries[0]); // क्वेरी की संख्या
for(int i = 0; i < q; i++) { // सभी क्वेरी के माध्यम से ट्रैवर्स करना
long ans = 0;
for(int j = queries[i][0]; j <= queries[i][1]; j++) // रेंज के माध्यम से ट्रैवर्स करना
ans |= arr[j]; // उत्तर की गणना करना
cout << ans << "\n";
}
return 0;
}
आउटपुट
7 3
इस दृष्टिकोण की समय जटिलता O(N*Q) है जहां N हमारे एरे का आकार है और Q क्वेरी की संख्या है। अब जैसा कि आप देख सकते हैं, यह जटिलता उच्च प्रतिबंधों के लिए काम नहीं करेगी, इसलिए अब हम अपने दृष्टिकोण को अनुकूलित करेंगे ताकि यह उच्च प्रतिबंधों के लिए भी काम करे।
कुशल दृष्टिकोण
इस दृष्टिकोण में, हम प्रीफिक्स बिट्स काउंट की गणना करेंगे, और फिर हम जांचेंगे कि क्या किसी संख्या का कोई विशेष बिट सेट है। यदि हां, तो हम इस बिट को उत्तर में रखते हैं; अन्यथा, हम इस बिट को छोड़ देते हैं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define bitt 32
#define MAX (int)10e5
int prefixbits[bitt][MAX];
void bitcount(int *arr, int n) { // प्रीफिक्स काउंट बनाना
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) { // उत्तर की गणना करना
long ans = 0; // ओवरफ्लो से बचने के लिए हम ans को 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); // हमारे एरे का आकार
bitcount(arr, n);
int queries[][2] = {{1, 3}, {4, 5}}; // दी गई क्वेरी
int q = sizeof(queries) / sizeof(queries[0]); // क्वेरी की संख्या
for (int i = 0; i < q; i++) {
cout << check(queries[i][0], queries[i][1]) << "\n";
}
return 0;
}
आउटपुट
7 3
इस दृष्टिकोण की समय जटिलता O(N) है, जहां N हमारे एरे का आकार है, इसलिए यह दृष्टिकोण उच्च प्रतिबंधों के लिए काम कर सकता है।
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम प्रीफिक्स बिट्स काउंट की गणना कर रहे हैं और इसे स्टोर कर रहे हैं। अब हम एक क्वेरी की गणना करते हैं, हम उस प्रीफिक्स काउंट के माध्यम से जाते हैं और l-1 के बिट काउंट को हटाते हैं ताकि हमारे पास रेंज [l, r] में संख्याओं के बिट्स की गिनती हो। अब चूंकि हम उन्हें जानते हैं, यदि किसी संख्या में कोई बिट सेट है, तो यदि आप इसे किसी अन्य संख्या के साथ बिटवाइज OR लेते हैं तो बिट सेट रहेगा। बिटवाइज OR के इस गुण का उपयोग करके हम जांचते हैं कि क्या बिट काउंट शून्य नहीं है, इसका मतलब है कि रेंज में सेट बिट वाली एक संख्या मौजूद है, इसलिए हम उस बिट को उत्तर में सेट करते हैं और लूप के माध्यम से जारी रखते हैं और अंत में उत्तर प्रिंट करते हैं।
निष्कर्ष
यह लेख दिए गए एरे के इंडेक्स रेंज [L, R] में बिटवाइज OR के लिए क्वेरी की गणना करने की समस्या को हल करता है। हमने इस समस्या के लिए C++ प्रोग्राम और इसे हल करने के पूर्ण दृष्टिकोण (सामान्य और कुशल) को भी सीखा। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख मददगार लगा होगा।
