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.

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.

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;
```

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.

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.

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 ?

If u have to print the bitwise AND of each subarray then there is no option other than O(n^{2})

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

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

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

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

did it in O(1) for each test case