Problem: Given an array, check that the pair-wise bitwise AND of all the elements of an array is zero.

The brute force approach is to just do what is given in the problem: bitwise AND each pair in the element, if it's not zero return false.

The time complexity will be O(N^2), where N is the length of the array.

Question 01: Given two numbers, what really happens when you perform bitwise AND?

Let's perform bitwise AND operation on 3 and 5.

Observe in the figure that, the result contains 1 bit, only if both the bits in operands were 1. That's the truth table of AND gate. I know xd.

To solve our problem we require that the result contains all the bits as 0, for each pair in the array. What if we just track the 1 bit after each operation and check that result should not contain any 1 bit? But how?

Question 02: Given two numbers, what really happens when you perform bitwise OR?

Let's perform bitwise OR operation on 3 and 5.

What can we infer from the result? That bitwise OR will tell us the positions of 1 bit in the result.

How can we use the two results, we learned above and solve the initial problem?

Consider a variable mask, for each element we perform bitwise AND with mask, then update mask, with the bitwise OR of mask with current element.

bool bitwiseAND(int arr[], int n){
  int mask = 0;
  for(int i=0;i<n;i++){
    if(mask & arr[i] !=0)
      return false;
 
    mask |= arr[i];
  }
  return true;
}

The variable mask contains the 1 bits, we found in all the previous elements, now if the bitwise AND of mask and current element is not equal to zero, that means the current element will not give 0 upon bitwise AND with the element that has 1 bit at a position which couldn't be countered with a 0 bit at that position of current element.

The time complexity in this approach will be O(N), where N is the length of the the array.

I'd suggest dry-running the above code on a valid example such as [3,8,48] and an counter example such as [3,4,5] while keeping a track on how the 1 bit changes in mask.

Extras:

1. How can you remove 1 bits from mask of any previous element using bitwise operation? Hint: XOR
2. Try to solve the Longest Nice Subarray problem as an application of this concept.