Write code using C++ to find the number of subarrays with bits or values ​​greater than or equal to K

In this article, we will briefly explain how to find the number of subarrays with bitwise OR>=K in C. So we have an array arr[] and an integer K, and we have to find the number of subarrays whose OR (bitwise OR) is greater than or equal to K. So here is the example of the given problem -

Input: arr[] = {1, 2, 3} K = 3
Output: 4

Bitwise OR of sub-arrays:
{1} = 1
{1, 2} = 3
{1, 2, 3} = 3
{2} = 2
{2, 3} = 3
{3} = 3
4 sub-arrays have bitwise OR ≥ 3
Input: arr[] = {3, 4, 5} K = 6
Output: 2

Ways to find the solution

Now we will use two different methods to solve the problem using C -

Brute force Crack

In this approach, we are just going to iterate through all the sub-arrays that can be formed and check if OR is greater than or equal to K. If yes, then we will add our answer.

Example

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = {1, 2, 3}; // given array.
    int k = 3;
    int size = sizeof(arr) / sizeof(int); // the size of our array.
    int answer = 0; // the counter variable.
    for(int i = 0; i < size; i++){
        int bitwise = 0; // the variable that we compare to k.
        for(int j = i; j < size; j++){ // all the subarrays starting from i.
            bitwise = bitwise | arr[j];
            if(bitwise >= k) // if bitwise >= k increment answer.
               answer++;
        }
    }
    cout << answer << "\n";
    return 0;
}

Output

4

This method is very simple, but it has its flaws, because this method is not good for higher constraints. constraints, it will take too much time because the time complexity of this approach is O(N *N), where N is the size of the given array, so now we will use an efficient method.

Efficient method

In this method we will use some properties of OR operator i.e. even if we add more numbers it will not decrease so if we go from i to j gets a subarray whose OR is greater than or equal to K, then each subarray containing the range {i,j} will have an OR greater than K. We are taking advantage of this property and improving our code.

Example

#include <bits/stdc++.h>
#define N 1000
using namespace std;
int t[4*N];
void build(int* a, int v, int start, int end){ // segment tree building
    if(start == end){
       t[v] = a[start];
       return;
    }
    int mid = (start + end)/2;
    build(a, 2 * v, start, mid);
    build(a, 2 * v + 1, mid + 1, end);
    t[v] = t[2 * v] | t[2 * v + 1];
}
int query(int v, int tl, int tr, int l, int r){ // for processing our queries or subarrays.
    if (l > r)
       return 0;
    if(tl == l && tr == r)
       return t[v];
    int tm = (tl + tr)/2;
    int q1 = query(2*v, tl, tm, l, min(tm, r));
    int q2 = query((2*v)+1, tm+1, tr, max(tm+1, l), r);
    return q1 | q2;
}
int main(){
    int arr[] = {1, 2, 3}; // given array.
    int k = 3;
    int size = sizeof(arr) / sizeof(arr[0]); // the size of our array.
    int answer = 0; // the counter variable.
    build(arr, 1, 0, size - 1); // building segment tree.
    for(int i = 0; i < size; i++){
        int start = i, end = size-1;
        int ind = INT_MAX;
        while(start <= end){ // binary search
            int mid = (start + end) / 2;
            if(query(1, 0, size-1, i, mid) >= k){ // checking subarray.
               ind = min(mid, ind);
               end = mid - 1;
            }
            else
               start = mid + 1;
        }
        if(ind != INT_MAX) // if ind is changed then increment the answer.
            answer += size - ind;
    }
    cout << answer << "\n";
    return 0;
}

Output

4

In this approach, we use binary search and segment tree, which helps reduce the time complexity from O( N*N) is reduced to O(Nlog(N)), which is very good. Now, unlike the previous procedure, this procedure can also be applied to larger constraints.

Conclusion

In this paper we solved a problem to find the number of subarrays with OR >= K using binary search and segment tree, time complex The degree is O(nlog(n)). 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. Hope this article is helpful to you.

The above is the detailed content of Write code using C++ to find the number of subarrays with bits or values ​​greater than or equal to K. For more information, please follow other related articles on the PHP Chinese website!