इस लेख में हम दिए गए रेंज में मौजूद उन तत्वों की संख्या खोजने की समस्या पर चर्चा करेंगे जिनका kवां बिट सेट है, उदाहरण के लिए:
इनपुट: arr[] = {4, 5, 7, 2}
क्वेरी 1: L = 2, R = 4, K = 4
क्वेरी 2: L = 3, R = 5, K = 1
आउटपुट: 0 1
हम इस समस्या को ब्रूट फोर्स दृष्टिकोण से हल करेंगे और देखेंगे कि क्या यह दृष्टिकोण उच्च प्रतिबंधों के लिए काम कर सकता है या नहीं। यदि नहीं, तो हम एक नए कुशल दृष्टिकोण के बारे में सोचने की कोशिश करेंगे।
ब्रूट फोर्स दृष्टिकोण
इस दृष्टिकोण में, हम केवल रेंज के माध्यम से जाएंगे और प्रत्येक तत्व के लिए जांचेंगे कि क्या उसका kवां बिट सेट है या नहीं, यदि हां, तो हम काउंट बढ़ाते हैं।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
#define MAX_BITS 32
bool Kset(int n, int k) { // जांचें कि क्या kवां बिट सेट है
if (n & (1 << (k - 1)))
return true;
return false;
}
int query(int L, int R, int K, int arr[]) {
int count = 0; // रेंज में मौजूद संख्या की गिनती रखने के लिए काउंटर
for (int i = L; i <= R; i++) { // रेंज को ट्रैवर्स करना
if (Kset(arr[i], K)) {
count++;
}
}
return count;
}
int main() {
int arr[] = {4, 5, 7, 2}; // दिया गया एरे
int n = sizeof(arr) / sizeof(arr[0]); // हमारे एरे का आकार
int queries[][3] = { // दिया गया L, R और k
{2, 4, 4},
{3, 5, 1}
};
int q = sizeof(queries) / sizeof(queries[0]); // क्वेरी की संख्या
for (int i = 0; i < q; i++) {
int L = queries[i][0] - 1;
int R = queries[i][1] - 1;
int K = queries[i][2];
cout << query(L, R, K, arr) << "\n";
}
return 0;
}
आउटपुट
0 1
उपरोक्त दृष्टिकोण की समय जटिलता O(N*Q) है जहां N हमारे एरे का आकार है और Q हमें दी गई क्वेरी की संख्या है। अब जैसा कि आप देख सकते हैं, यह दृष्टिकोण उच्च प्रतिबंधों के लिए उपयुक्त नहीं है क्योंकि इसमें बहुत अधिक समय लगेगा, इसलिए अब हम कुशल दृष्टिकोण का प्रोग्राम बनाने की कोशिश करेंगे।
कुशल दृष्टिकोण
इस दृष्टिकोण में, हम एक 2-D प्रीफिक्स सम एरे बनाए रखेंगे जो प्रत्येक इंडेक्स तक उपयोग किए गए प्रत्येक बिट की गिनती रखेगा, और फिर हम उत्तर की गणना O(1) जटिलता में कर सकते हैं।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
#define bits 32 // बिट्स की संख्या
int P[100000][bits+1];
bool Kset(int n, int k) {
if (n & (1 << (k - 1)))
return true;
return false;
}
void prefixArray(int n, int arr[]) { // प्रीफिक्स एरे बनाना
for (int i = 0; i <= bits; i++) {
P[0][i] = 0; // प्रत्येक बिट की प्रारंभिक गिनती = 0 सेट करना
}
for (int i = 0; i < n; i++) {
for (int j = 1; j <= bits; j++) {
bool flag = Kset(arr[i], j);
if (i) // हम पिछली गिनती को नवीनतम गिनती (0) में जोड़ते हैं
P[i][j] = P[i - 1][j];
if (flag) { // यदि jवां बिट सेट है तो हम गिनती बढ़ाते हैं
P[i][j]++;
}
}
}
}
int query(int L, int R, int K) {
if (L) // यदि L 0 के बराबर नहीं है तो हम R पर प्रीफिक्स को L-1 पर प्रीफिक्स से घटाकर लौटाते हैं
return P[R][K] - P[L - 1][K];
else
return P[R][K];
}
int main() {
int arr[] = {8, 9, 1, 3}; // दिया गया एरे
int n = sizeof(arr) / sizeof(arr[0]); // दिए गए एरे का आकार
int queries[][3] = {
{1, 3, 4},
{2, 4, 1}
};
prefixArray(n, arr); // प्रीफिक्स एरे बनाने के लिए फंक्शन कॉल करना
int q = sizeof(queries) / sizeof(queries[0]); // क्वेरी की संख्या
for (int i = 0; i < q; i++) {
int L = queries[i][0] - 1;
int R = queries[i][1] - 1;
int K = queries[i][2];
cout << query(L, R, K) << "\n";
}
return 0;
}
आउटपुट
2 3
चूंकि हम प्रीफिक्स एरे को बनाए रख रहे हैं जो हमें O(1) में उत्तर खोजने में मदद कर रहा है, इसलिए हमारी समय जटिलता काफी कम होकर O(N) हो जाती है, जहां N हमारे दिए गए एरे का आकार है।
उपरोक्त कोड की व्याख्या
इस प्रोग्राम में, हम एरे के प्रत्येक इंडेक्स के लिए एक प्रीफिक्स काउंटर बनाए रखते हैं जो इंडेक्स तक उपयोग किए गए प्रत्येक बिट की गिनती करता है। हम इस गिनती को अपने एरे के लिए बनाते हैं। अब चूंकि हमारे पास प्रत्येक बिट का प्रीफिक्स काउंट स्टोर है, इसलिए kवें बिट की गिनती के लिए, हमें kवें बिट के प्रीफिक्स काउंट को R इंडेक्स तक kवें बिट के प्रीफिक्स काउंट से L-1 इंडेक्स तक घटाना होगा और वह हमारा उत्तर है।
निष्कर्ष
इस लेख में, हम Kवें बिट सेट के साथ रेंज में एरे तत्वों की संख्या के लिए क्वेरी हल करने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और इसे हल करने के पूर्ण दृष्टिकोण (सामान्य और कुशल) को भी सीखा। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख मददगार लगा होगा।
