Skip to main content
Back to problems
#2939
Medium Algorithms

Maximum xor product

Math Greedy Bit Manipulation
29.6% acceptance
Feb 25, 2026
272
73
Given three integers a, b, and n, return the maximum value of (a XOR x) * (b XOR x) where 0 <= x < 2n. Since the answer may be too large, return it modulo 109 + 7. Note that XOR is the bitwise XOR operation.

Solution

Rust
Time O(n)
Space O(1)
LeetCode
solution.rs 
impl Solution {
  pub fn maximum_xor_product(a: i64, b: i64, n: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let mut ra = a;
    let mut rb = b;
    // For bits 0..n-1, we can freely choose x bits
    for i in (0..n).rev() {
      let bit = 1i64 << i;
      let a_bit = (ra >> i) & 1;
      let b_bit = (rb >> i) & 1;
      if a_bit == b_bit {
        // Set this bit to 1 in both (XOR with x=1 for this bit)
        ra |= bit;
        rb |= bit;
      } else {
        // Give bit to the smaller to equalize
        if ra < rb {
          ra |= bit;
          rb &= !bit;
        } else {
          rb |= bit;
          ra &= !bit;
        }
      }
    }
    ((ra % MOD) * (rb % MOD) % MOD) as i32
  }
}