Count Number of Maximum Bitwise-OR Subsets

Count Number of Maximum Bitwise-OR Subsets

What is this problem about?

Given an array of integers, you first need to find the maximum possible bitwise OR value that can be formed by any subset of the elements. Then, you need to count how many non-empty subsets result in that maximum OR value.

Why is this asked in interviews?

This "Medium" problem is used by BNY Mellon, Citadel, and Microsoft to test a candidate's understanding of Bit Manipulation and Backtracking (or Power Set generation). It requires you to understand that the bitwise OR of all elements in the array is the highest possible OR value. The second step tests your ability to explore the subset space efficiently.

Algorithmic pattern used

The pattern is Bitwise OR properties combined with Recursion (Backtracking) or Iterative Subset Generation.

1. Calculate the "target" maximum OR by ORing all elements in the array once.
2. Use a recursive function to explore all $2^n$ subsets.
3. In each recursive step, maintain the current OR value. If it equals the target, increment the global count.
4. Alternatively, use bit manipulation to iterate through all integers from 1 to $2^n - 1$ to represent subsets.

Example explanation

Array: [3, 1]

1. Max OR: $3 | 1 = 3$ (binary 11 | 01 = 11).
2. Subsets:
   • {3}: OR = 3. (Match!)
   • {1}: OR = 1.
   • {3, 1}: OR = 3. (Match!) Count: 2.

Common mistakes candidates make

One common mistake is trying to find the max OR using complex combinations instead of just ORing everything. Another is not considering the base case correctly in recursion, potentially leading to double-counting. For arrays with up to 16 elements, $2^{16}$ is small enough for brute force, but for larger $n$, candidates might mistakenly try to use DP, which doesn't work well for bitwise OR due to the lack of inverse operations.

Interview preparation tip

Remember that for bitwise OR, adding more elements to a subset can only increase or keep the OR value the same (it never decreases). This "monotonic" property is very useful for pruning or understanding the bounds of the problem.