Is Maximum Product of Two Integers With No Common Bits easy or hard?

This problem is generally classified as Medium difficulty. The brute force solution is straightforward, but recognizing how to optimize compatibility checks using bit manipulation and mask DP requires stronger algorithmic insight.

Maximum Product of Two Integers With No Common Bits Python/Java solution

Implementation typically computes a bitmask for each integer and then applies either a brute force pair comparison or a DP‑based lookup for compatible masks. The logic translates directly across Python, Java, C++, and Go because the core operations rely on standard bitwise operators such as '&' and shifts.

How to solve Maximum Product of Two Integers With No Common Bits in O(n)?

Near‑linear performance is achieved by preprocessing masks and using a DP table indexed by bit patterns. After building the table that stores the maximum value for each mask and its submasks, you can check the best compatible partner for each number using complement masks. This avoids scanning the full array for each element.

What is the best approach for Maximum Product of Two Integers With No Common Bits?

The most efficient approach uses bitmasking combined with dynamic programming. Each integer is treated as a bitmask, and a DP table stores the maximum value for each mask or its submasks. This allows quick lookup of numbers whose bits do not overlap with a given mask, avoiding the O(n^2) pair comparison used in brute force solutions.

Is Maximum Product of Two Integers With No Common Bits asked at Google/Amazon/Meta?

Bit manipulation and mask compatibility problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving disjoint bitmasks, subset DP, or maximizing products or lengths under bit constraints are common in coding rounds.

What data structure is used in Maximum Product of Two Integers With No Common Bits?

The solution primarily uses arrays or hash maps to store the maximum value for each bitmask. Bitwise operations such as AND and complement masks are used to test compatibility between integers. Dynamic programming tables indexed by masks are often used for the optimized version.

What is the time complexity of Maximum Product of Two Integers With No Common Bits?

The brute force solution runs in O(n^2) time because it checks every pair of numbers and performs a bitwise AND operation. An optimized solution using bitmask DP runs in roughly O(n + B * 2^B) time, where B is the number of bits considered, significantly reducing repeated compatibility checks.

Description Hints 7 Video 13:23

3670. Maximum Product of Two Integers With No Common Bits

Medium15.1% acceptance

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 <= 10⁵
1 <= nums[i] <= 10⁶

Topics

Hints open one at a time

Hint 1

Think of each number as a mask: treat nums[i] as a bitmask.

Hint 2

Create an array dp of size 1 << B, where B is your bit‑width.

Hint 3

Initialize dp[mask] to the maximum nums[i] exactly equal to that mask, or 0 if none.

Hint 4

For each m, propagate to all its super‑masks M: dp[m] = max(dp[m], dp[M])

Hint 5

For a number x with mask mx, compute its "complement mask" as cm = ~mx & ((1 << B)-1).

Hint 6

The best disjoint partner is then dp[cm].

Hint 7

Loop over all x in nums, look up dp[cm], and track the maximum x * partner.

3670. Maximum Product of Two Integers With No Common Bits

Topics

Hints open one at a time

Similar problems