Maximum product of two integers with no common bits

Array Dynamic Programming Bit Manipulation

15.1% acceptance

Mar 9, 2026

100

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_product(nums: Vec<i32>) -> i64 {
    // All values fit in 20 bits (nums[i] <= 10^6 < 2^20).
    // Strategy: SOS (Sum-Over-Subsets) DP to build best[mask] = maximum
    // value present in nums that is a submask of `mask`.
    // Then for each x, the best disjoint partner is best[~x & MAXM].
    // Total complexity: O(20 * 2^20) ≈ 20M ops — independent of n.
    const BITS: usize = 20;
    const MAXM: usize = (1 << BITS) - 1; // 0xFFFFF

    // Step 1: seed best[v] = v for every value present in nums.
    let mut best = vec![0i32; MAXM + 1];
    for &v in &nums {
      let v = v as usize;
      best[v] = best[v].max(v as i32);
    }

    // Step 2: SOS DP — propagate maximums up to supersets.
    // After this pass, best[mask] = max value in nums that is a submask of mask.
    for b in 0..BITS {
      for mask in 0..=MAXM {
        if mask & (1 << b) != 0 {
          let sub = mask ^ (1 << b);
          if best[sub] > best[mask] {
            best[mask] = best[sub];
          }
        }
      }
    }

    // Step 3: for each x, look up the best y with x & y == 0 in O(1).
    // Since x & x != 0 for x >= 1, x is never its own complement submask.
    let mut ans = 0i64;
    for &v in &nums {
      let complement = (!v as usize) & MAXM;
      let y = best[complement] as i64;
      let candidate = v as i64 * y;
      if candidate > ans {
        ans = candidate;
      }
    }
    ans
  }
}