इस लेख में हम दिए गए रेंज में मौजूद तत्वों की संख्या को खोजने की समस्या पर चर्चा करेंगे, जिनमें kth बिट सेट है, उदाहरण के लिए -
Input : arr[] = { 4, 5, 7, 2 }
Query 1: L = 2, R = 4, K = 4
Query 2: L = 3, R = 5, K = 1
Output :
0
1 हम इस समस्या को एक क्रूर बल दृष्टिकोण से हल करने जा रहे हैं और देखें कि यह दृष्टिकोण उच्च बाधाओं के लिए काम कर सकता है या नहीं। यदि नहीं, तो हम एक नए कुशल दृष्टिकोण के बारे में सोचने की कोशिश करते हैं।
क्रूर फ़ोर्स अप्रोच
इस दृष्टिकोण में, हम केवल सीमा के माध्यम से जाने वाले हैं और प्रत्येक तत्व की जांच करेंगे कि यदि यह kth बिट सेट है या नहीं, यदि हाँ, तो हम गिनती बढ़ाते हैं।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
#define MAX_BITS 32
bool Kset(int n, int k) { // to check if kth bit is set
if (n & (1 << (k - 1)))
return true;
return false;
}
int query(int L, int R, int K, int arr[]) {
int count = 0; // counter to keep count of number present in the range
for (int i = L; i <= R; i++) { // traversing the range
if (Kset(arr[i], K)) {
count++;
}
}
return count;
}
int main() {
int arr[] = { 4, 5, 7, 2 }; // given array
int n = sizeof(arr) / sizeof(arr[0]); // size of our array
int queries[][3] = { // given L, R and k
{ 2, 4, 4 },
{ 3, 5, 1 }
};
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
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
उपरोक्त दृष्टिकोण में ओ (एन * क्यू) की समय जटिलता है जहां एन हमारे सरणी का आकार है और क्यू अब हमें दिए गए प्रश्नों की संख्या है; जैसा कि आप देख सकते हैं, यह दृष्टिकोण उच्च बाधाओं के लिए उपयुक्त नहीं है क्योंकि इसमें बहुत अधिक समय लगेगा इसलिए अब हम कुशल दृष्टिकोण का कार्यक्रम बनाने का प्रयास करेंगे।
कुशल दृष्टिकोण
इस दृष्टिकोण में, हम एक 2-डी उपसर्ग योग सरणी बनाए रखेंगे जो प्रत्येक इंडेक्स तक उपयोग किए जाने वाले प्रत्येक बिट की गिनती रखेगा, और फिर हम ओ (1) जटिलता में उत्तर की गणना कर सकते हैं।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
#define bits 32 // number of bits
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[]) { // building the prefix array
for (int i = 0; i <= bits; i++) {
P[0][i] = 0; // setting every bits initial count = 0
}
for (int i = 0; i < n; i++) {
for (int j = 1; j <= bits; j++) {
bool flag = Kset(arr[i], j);
if (i) // we add previous count to the latest count(0)
P[i][j] = P[i - 1][j];
if (flag) { // if jth bit is set so we increase the count
P[i][j]++;
}
}
}
}
int query(int L, int R, int K) {
if (L) // if L not equal to 0 then we return the prefix at R subtracted with prefix at L-1
return P[R][K] - P[L - 1][K];
else
return P[R][K];
}
int main() {
int arr[] = { 8, 9, 1, 3 }; // given array
int n = sizeof(arr) / sizeof(arr[0]); // size of given array
int queries[][3] = {
{ 1, 3, 4 },
{ 2, 4, 1 }
};
prefixArray(n, arr); // calling the function to create prefix array
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
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
चूंकि हम उपसर्ग सरणी को बनाए रखते हैं जो ओ (1) में उत्तर खोजने में हमारी सहायता कर रहा है, इसलिए इसके द्वारा, हमारी समय जटिलता ओ (एन) तक कम हो जाती है, जहां एन हमारे दिए गए सरणी का आकार है।
उपरोक्त कोड की व्याख्या
इस कार्यक्रम में, हम सरणी के प्रत्येक सूचकांक के लिए एक उपसर्ग काउंटर बनाए रखते हैं जो सूचकांक तक उपयोग किए जाने वाले प्रत्येक बिट की गणना करता है। हम अपने सरणी के लिए इस गिनती का निर्माण करते हैं क्योंकि हमारे पास हमारे पास संग्रहीत प्रत्येक बिट की उपसर्ग संख्या है, इसलिए kth बिट गणना के लिए, हमें kth बिट की उपसर्ग संख्या को R अनुक्रमणिका तक घटाना होगा, kth बिट की उपसर्ग गणना के साथ L- 1 अनुक्रमणिका और वह हमारा उत्तर है।
निष्कर्ष
इस लेख में, हम Kth बिट सेट के साथ एक श्रेणी में सरणी तत्वों की संख्या के लिए क्वेरी को हल करने के लिए एक समस्या का समाधान करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (सामान्य और कुशल) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे C, java, python, और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह लेख मददगार लगा होगा।