Code written in C++ to query the number of array elements in a range that has the Kth bit set

In this article we will discuss the problem of finding the number of elements in a given range that have the k-th bit set, e.g. −

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

We will pass A brute force approach to this problem and see if this approach works with higher constraints. If it doesn't work, then we try to think of a new efficient method.

Brute Force Method

In this method we just iterate through the range and check if the kth bit of each element is set and if so, increment the count.

Example

#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;
}

Output

0
1

The time complexity of the above method is O(N*Q), where N is the size of the array and Q is the given number of queries ; As you can see, this approach won't work for higher constraints because it will take too much time, so now we will try to make an efficient program.

Efficient method

In this method we will maintain a 2D prefix sum array which will keep the number of bits used at each index position and we can do it in O( The answer is calculated within the complexity of 1).

Example

#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;
}

Output

2
3

Since we are maintaining a prefix array that helps us find the answer in O(1) time complexity, our time complexity is greatly This is reduced to O(N), where N is the size of the given array.

Explanation of the above code

In this program, we maintain a prefix counter for each index of the array, which is used to count each number of bits used before that index. Now, we have stored the prefix count for each digit, so for the k-th count, we need to subtract the k-th prefix at the L-1 index from the k-th prefix count at the R-th index Count, that's our answer.

Conclusion

In this article, we addressed the problem of solving a query for a range of array elements with the Kth bit set. We also learned the C program for this problem and our complete approach to solving it (both trivial and efficient). We can write the same program in other languages ​​like C, Java, Python and others. Hope you find this article helpful.

The above is the detailed content of Code written in C++ to query the number of array elements in a range that has the Kth bit set. For more information, please follow other related articles on the PHP Chinese website!