Watch 8 video solutions for Maximum Product of Two Integers With No Common Bits, a medium level problem involving Array, Dynamic Programming, Bit Manipulation. This walkthrough by Sanyam IIT Guwahati has 1,119 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums.
Your task is to find two distinct indices i and j such that the product nums[i] * nums[j] is maximized, and the binary representations of nums[i] and nums[j] do not share any common set bits.
Return the maximum possible product of such a pair. If no such pair exists, return 0.
Example 1:
Input: nums = [1,2,3,4,5,6,7]
Output: 12
Explanation:
The best pair is 3 (011) and 4 (100). They share no set bits and 3 * 4 = 12.
Example 2:
Input: nums = [5,6,4]
Output: 0
Explanation:
Every pair of numbers has at least one common set bit. Hence, the answer is 0.
Example 3:
Input: nums = [64,8,32]
Output: 2048
Explanation:
No pair of numbers share a common bit, so the answer is the product of the two maximum elements, 64 and 32 (64 * 32 = 2048).
Constraints:
2 <= nums.length <= 1051 <= nums[i] <= 106Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n²) | O(1) | Small arrays or when first reasoning about the bitwise compatibility condition |
| Bitmask Compression + DP | O(n + B * 2^B) | O(2^B) | When bit width is limited and you want faster compatibility lookups than checking every pair |