Bitwise AND of all subarrays

1

Is there any efficient Algorithm to find BITWISE AND of all subarrays of given Integer array . I am doing it using a O(N^2) algorithm. Please help.

2

The question is incomplete. No one will ask you to find the bitwise and of all subarrays - Since the number of subarrays for an array of size N will be \frac{N\times(N+1)}{2}.
They could ask you a little more, like find the number of distinct values or bitwise-or of
bitwise-and of all subarrays.

1 Like
3

Just do bitwise AND of whole array -
arr = [1,2,3]
All possible subarrays are
{1}, {2}, {3}, {1, 2}, {2, 3} and {1, 2, 3}
ANDs of these subarrays are 1, 2, 3, 0, 2, 0.
AND of these ANDs is 0.

as we know X & X & X = X

so answer will be Btwise AND of whole array -

int ans = a[0];
    for (int i = 0; i < n; ++i) 
        ans &= a[i];  
    cout<<ans;
4

I found this answer on GFG but , my question is i want to print the BITWISE AND of every subarray. i.e consider a subarray , take bitwise AND of all elemnts, this will be the BITWISE AND operation on all the elements of this subarray , then print it.

5

My question is i want to print the BITWISE AND of every subarray. i.e consider a subarray , take bitwise AND of all elemnts, this will be the BITWISE AND operation on all the elements of this subarray , then print it.

6

I am doing this by building a 2D array , and storing the bitwise AND of the sub array from i to j . This take , in worst case o(N^2) time , is there a better way ?

7

If u have to print the bitwise AND of each subarray then there is no option other than O(n2)

8

Then there is no efficient algorithm I guess.
Here’s how you’re gonna do it in C.

C Code 
#include <stdio.h>

void findBitwiseAnd(int a[], int n) {
    for(int i = 0; i < n; i++) {
        int temp = a[i];
        for(int j = i; j < n; j++) {
            temp &= a[j];
            printf("Bitwise-AND of subarray from %d to %d = %d\n", i + 1, j + 1, temp);
        }
    }
}

int main() {
    int a[] = {1, 2, 3};
    findBitwiseAnd(a, 3);
    return 0;
}
9

I don’t think there’s an efficient algorithm for finding subarray in less than O(n^2) :slightly_smiling_face:

10

how to find bitwise xor of bitwise and of all subarrays?

11

2&3=2
4&5&6&7=4
8&9&10&11&12&13&14&15=8
but
1&2=0
3&4&5&6&7=0
1&2&3&4=0
1&2&3&4&5&6&7&8=0

12

did it in O(1) for each test case :wink: