LeetCode 3670 - Maximum Product of Two Integers With No Common Bits

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Bit Manipulation

Solution

Problem Understanding

The problem asks us to find the maximum product of two distinct elements in an array of integers, under the constraint that their binary representations do not share any set bits. In other words, for any two numbers nums[i] and nums[j] that we consider, the bitwise AND of the two numbers must be zero (nums[i] & nums[j] == 0). The input is an array of integers, each ranging from 1 to 10^6, with the array length up to 10^5. The output is a single integer representing the largest product that satisfies the no-common-bits condition, or 0 if no such pair exists.

Key points to note are that the numbers are positive integers and distinct indices are required. Edge cases include arrays where all numbers share common bits (resulting in 0) or arrays with very large numbers that could potentially cause integer overflow in languages with fixed integer sizes. The constraints indicate that a naive O(n^2) approach would likely be too slow, so an efficient algorithm is necessary.

Approaches

The brute-force approach would involve checking every pair of numbers in the array. For each pair (nums[i], nums[j]), we check if nums[i] & nums[j] == 0 and, if so, compute their product and track the maximum. This approach is correct because it examines all possible pairs, ensuring the optimal pair is found, but it has a time complexity of O(n^2), which is too slow for n up to 10^5.

The optimal approach leverages the observation that each number can be represented by a 20-bit mask (since the maximum number is 10^6, which is less than 2^20). We can store, for each possible bitmask, the largest number in the array that has that exact bitmask. Then, we check pairs of masks to find those that do not share any common bits and calculate their product. Since the number of unique masks is limited by the number of bits (up to 2^20), this reduces the number of comparisons drastically. Additionally, a bit-level subset manipulation can be used to further optimize checks against incompatible masks.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Checks all pairs for no-common-bits condition, too slow for n = 10^5
Optimal	O(n + 2^b * b) where b = 20	O(2^b)	Uses bitmask mapping to track largest numbers per mask, only compares compatible masks

Algorithm Walkthrough

Initialize a dictionary mask_to_max that maps a bitmask to the maximum number with that mask.
For each number in nums, compute its bitmask representation. If the mask is not already in mask_to_max or if the number is greater than the stored value for that mask, update mask_to_max.
Extract all masks stored in mask_to_max and their corresponding maximum numbers.
Initialize max_product to 0.
Iterate through all pairs of masks. For each pair (mask1, mask2), check if mask1 & mask2 == 0. If true, calculate the product of the corresponding numbers and update max_product if it is larger than the current value.
Return max_product after all pairs are considered.

Why it works: By storing the maximum number for each unique bitmask, we ensure that we only consider the largest possible number for each mask when computing products. Checking mask pairs guarantees no shared bits, satisfying the problem constraint. This efficiently reduces the search space from O(n^2) to O(2^b * b), which is manageable since b ≤ 20.

Python Solution

PythonRun

In this implementation, each number is converted to a bitmask. The dictionary mask_to_max ensures we only keep the largest number for each unique bit pattern. We then check all mask pairs for compatibility, updating max_product accordingly.

Go Solution

Go

Go-specific notes: We handle integer overflow by using int64 for the product. The map maskToMax stores integers, and we convert to int64 only when computing products. Slices are used to iterate through masks, and initialization handles empty maps gracefully.

Worked Examples

Example 1: nums = [1,2,3,4,5,6,7]

Step	Number	Mask (binary)	mask_to_max
1	1	0001	{1:1}
2	2	0010	{1:1, 2:2}
3	3	0011	{1:1, 2:2, 3:3}
4	4	0100	{1:1, 2:2, 3:3, 4:4}
...	...	...	...

Compatible masks: 3 (0011) & 4 (0100) => product 12, maximum.

Example 2: nums = [5,6,4]

All pairs have overlapping bits, so no compatible pair exists, return 0.

Example 3: nums = [64,8,32]

Masks: 64 => 1000000, 32 => 0100000, 8 => 0010000. Any pair is compatible. Maximum product is 64*32 = 2048.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + 2^b * b)	O(n) to compute masks, O(2^b * b) to compare mask pairs where b ≤ 20
Space	O(2^b)	Stores the largest number for each mask, limited by 20 bits

The algorithm is efficient because the maximum number of unique masks is limited by the bit width of the integers, not the array length.

Test Cases

PythonRun

Test	Why
[1,2,3,4,5,6,7]	mix of compatible and incompatible pairs
[5,6,4]	all incompatible pairs, returns 0
[64,8,32]	all compatible pairs, maximum product is large
[1,2]	minimum array size