Maximum Product of Two Integers With No Common Bits - Solution & Explanation

Problem Overview: You are given an array of integers and need to pick two numbers whose binary representations share no common set bits. In other words, (a & b) == 0. Among all such valid pairs, return the maximum possible product.

Approach 1: Brute Force Pair Check (O(n²) time, O(1) space)

The most direct solution checks every pair of integers in the array. For each pair (nums[i], nums[j]), compute nums[i] & nums[j]. If the result is zero, the two numbers have no overlapping bits, so update the maximum product with nums[i] * nums[j]. This approach is simple and demonstrates the key bit manipulation condition clearly. However, the nested loop requires O(n²) comparisons, which becomes expensive when the array grows large.

Approach 2: Bitmask Compression + Dynamic Programming (O(n + B * 2^B) time, O(2^B) space)

A more scalable approach uses bitmasking to represent each number’s set bits. Treat the integer itself as its mask. Instead of comparing every pair directly, maintain a table where dp[mask] stores the maximum number in the array that exactly matches that mask. Then use subset dynamic programming to propagate the maximum value for all submasks. This allows quick lookup of the best number compatible with another mask.

For each number with mask m, compute the complement mask containing bits not used by m. Any valid partner must be a submask of that complement. Because the DP table already stores the best value for every submask, you can retrieve the best compatible number in constant time and update the product. This avoids scanning the entire array for each element and converts repeated compatibility checks into table lookups.

This technique combines ideas from bit manipulation and dynamic programming. It works best when the number of possible bit positions (B) is reasonably small, allowing the 2^B state space to remain manageable.

Both methods rely on representing integers as bitmasks and using the property that a & b == 0 indicates no overlapping bits. The optimized method reduces repeated pair checks and is commonly used in problems involving mask compatibility within array inputs.

Recommended for interviews: Start by describing the brute force pair check since it directly reflects the problem definition. Then improve it using a bitmask DP or mask‑based lookup strategy. Interviewers typically expect candidates to recognize the (a & b) == 0 compatibility rule and reduce pair comparisons using bit manipulation techniques.