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