Query the bitwise OR operation of a given array within the index range using C++

In this article, we are given an array of integers. Our task is to find the bitwise OR of all numbers in a given range, for example,

Input: arr[] = {1, 3, 1, 2, 3, 4}, q[] = {{0, 1}, {3, 5}}
Output:
3
7
1 OR 3 = 3
2 OR 3 OR 4 = 7
Input: arr[] = {1, 2, 3, 4, 5}, q[] = {{0, 4}, {1, 3}}
Output:
7
7

In the given problem we will use brute force approach to solve it and then check if it can be applied to higher constraints. If not, then we will optimize our method to fit the higher constraints.

Brute Force Method

In this method we just iterate through each range and calculate bitwise OR all the numbers in that range and print our answer.

Example

#include <bits/stdc++.h>
using namespace std;
int main() {
   int arr[] = { 7, 5, 3, 5, 2, 3 };
   int n = sizeof(arr) / sizeof(int); // size of our array
   int queries[][2] = { { 1, 3 }, { 4, 5 } }; // given queries
   int q = sizeof(queries) / sizeof(queries[0]); // number of queries
   for(int i = 0; i < q; i++) { // traversing through all the queries
      long ans = 0;
      for(int j = queries[i][0]; j <= queries[i][1]; j++) // traversing through the range
         ans |= arr[j]; // calculating the answer
      cout << ans << "\n";
   }
   return 0;
}

Output

7
3

The time complexity of this method is O(N*Q), where N is the size of the array and Q is the current number of queries , as you can see, this complexity does not hold for higher constraints, so now we will optimize our method so that it also works for higher constraints.

Efficient method

In this method we will count the number of prefix digits and then check if the number has a specific set of bits. If yes, then we put this point into the answer; otherwise, we keep this point.

Example

#include <bits/stdc++.h>

using namespace std;
#define bitt 32
#define MAX (int)10e5

int prefixbits[bitt][MAX];
void bitcount(int *arr, int n) { // making prefix counts
   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) { // calculating the answer
   long ans = 0; // to avoid overflow we are taking ans as 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); // size of our array
   bitcount(arr, n);
   int queries[][2] = {{1, 3}, {4, 5}}; // given queries
   int q = sizeof(queries) / sizeof(queries[0]); // number of queries
   for (int i = 0; i < q; i++) {
      cout << check(queries[i][0], queries[i][1]) << "\n";
   }
   return 0;
}

Output

7
3

The time complexity of this method is O(N), where N is the size of the array, so this method Higher constraints can be applied.

Explanation of the above code

In this method, we count the number of prefix digits and store it. Now we compute a query where we iterate over that prefix count and remove the bit count of l-1 so that we have the bit count of a number in the range [l, r] since we know if a bit is set in any number therefore, If you bitwise OR it with any other number then the bit will remain set so using this property of bitwise OR we check if the bit count is not zero which means there is a number in the range with the set bit , so we set the answer bit and continue the loop, finally printing the answer.

Conclusion

This article solves the problem of computing a bitwise OR query in the index range [L, R] given an array. We also learned a C program to solve this problem and a complete way to solve this problem (normal and efficient). We can write the same program in other languages ​​such as C, java, python and other languages. We hope this article was helpful to you.

The above is the detailed content of Query the bitwise OR operation of a given array within the index range using C++. For more information, please follow other related articles on the PHP Chinese website!