Bitwise ORs of Subarrays

Bitwise ORs of Subarrays

What is this problem about?

Given an array, you need to find the total number of unique values that can be formed by taking the bitwise OR of all possible contiguous subarrays. Unlike subsequences, subarrays must be a continuous segment of the original array. This problem is tricky because the number of subarrays is $O(N^2)$, but you need an approach that is more efficient for large arrays.

Why is this asked in interviews?

This is a frequent question at Google and Amazon. It tests your ability to optimize an $O(N^2)$ problem using the property that bitwise OR is a non-decreasing operation. As you expand a subarray, the number of set bits in its OR sum can only increase. Since an integer only has 30-32 bits, the number of unique OR values ending at any position i is actually very small (at most 30-32).

Algorithmic pattern used

This uses a Dynamic Programming or Set-based approach. For each index i, you maintain a set of all possible bitwise ORs of subarrays ending at i. To get the set for i+1, you take every value in the current set, OR it with arr[i+1], and add arr[i+1] itself. Because the number of unique values in each set is capped by the number of bits (e.g., 32), the overall complexity becomes $O(N imes 32)$, which is essentially $O(N)$.

Example explanation

Array: [1, 2, 4]

1. At index 0: Set = {1}. Global Set = {1}.
2. At index 1: New values are 1|2 and 2. Set = {3, 2}. Global Set = {1, 2, 3}.
3. At index 2: New values are 3|4, 2|4, and 4. Set = {7, 6, 4}. Global Set = {1, 2, 3, 4, 6, 7}. Total unique values = 6.

Common mistakes candidates make

The most common mistake is using a nested loop to calculate every subarray's OR sum, resulting in an $O(N^2)$ time complexity that will time out. Another mistake is not using a set to keep track of unique values, which makes the counting process difficult.

Interview preparation tip

Remember the "32-bit rule": many bitwise problems on arrays can be reduced from $O(N^2)$ to $O(32N)$ because an integer can only be "updated" 32 times before it becomes all 1s or reaches its maximum bits.