3670. Maximum Product of Two Integers With No Common Bits
Description
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] <= 106
Solutions
Solution 1
Thinking
Pick two numbers with AND zero and maximize their product. Pair enumeration is quadratic; the bit width is small enough for a subset DP.
Let \(f[s]\) be the largest input that is a subset of \(s\). For each \(x\), query the complement mask in \(f\) and update the product.
Seed \(f[x]\) from the input, then SOS-max over bits so \(f[s]\) absorbs every submask. A complement query guarantees disjoint ones.
1 | |
1 | |
1 | |
1 | |