Maximum Xor Product

Medium
1334.

Maximum Xor Product

Maximum Xor Product is a medium coding problem on math, greedy and bit manipulation, asked in Amazon and Google interviews.

Given three integers a, b and n, find the maximum value of (a XOR x) * (b XOR x) over all integers x with 0 <= x < 2^n.

The product can be huge, so return the maximum product taken modulo 10^9 + 7 (maximise the true product first, then reduce it).

CodeKairo bound: the original allows a, b < 2^50 and n <= 50; here a, b < 2^30 and n <= 30 so every input fits a 32-bit integer.

Example 1

Input
a = 3, b = 9, n = 2
Output
27
Explanation
`x = 0` gives 3 × 9 = 27; `x = 1` gives 2 × 8 = 16, `x = 2` gives 1 × 11 and `x = 3` gives 0 × 10.

Example 2

Input
a = 0, b = 0, n = 3
Output
49
Explanation
`x = 7` turns both into 7.

Example 3

Input
a = 1000000000, b = 1000000000, n = 0
Output
49
Explanation
Only `x = 0` is allowed; 10^18 modulo 10^9 + 7 is 49.

Constraints

  • 0 <= a, b < 2^30
  • 0 <= n <= 30
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} a
 * @param {number} b
 * @param {number} n
 * @return {number}
 */
var maximumXorProduct = function(a, b, n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Xor Product — Solution in Python, Java & C++

Maximum Xor Product solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on math and greedy.

Maximum Xor Product is a medium coding problem on math, greedy and bit manipulation, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Math, Greedy, Bit Manipulation
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given three integers a, b and n, find the maximum value of (a XOR x) * (b XOR x) over all integers x with 0 <= x < 2^n.

The product can be huge, so return the maximum product taken modulo 10^9 + 7 (maximise the true product first, then reduce it).

CodeKairo bound: the original allows a, b < 2^50 and n <= 50; here a, b < 2^30 and n <= 30 so every input fits a 32-bit integer.

Example 1

Input: a = 3, b = 9, n = 2
Output: 27
Explanation: `x = 0` gives 3 × 9 = 27; `x = 1` gives 2 × 8 = 16, `x = 2` gives 1 × 11 and `x = 3` gives 0 × 10.

Example 2

Input: a = 0, b = 0, n = 3
Output: 49
Explanation: `x = 7` turns both into 7.

Example 3

Input: a = 1000000000, b = 1000000000, n = 0
Output: 49
Explanation: Only `x = 0` is allowed; 10^18 modulo 10^9 + 7 is 49.

Constraints

  • 0 <= a, b < 2^30
  • 0 <= n <= 30

Hints for Maximum Xor Product

  1. Hint 1

    x can only change the lowest n bits of a and b; everything above stays fixed.

  2. Hint 2

    Within those bits, if a and b agree at a position, x can make both bits 1 — always worth it. If they disagree, exactly one of them gets the 1 whatever x is.

  3. Hint 3

    For disagreeing bits the sum a' + b' is fixed, and a product with a fixed sum is largest when the two factors are as close as possible: from the top bit down, give each disagreeing bit to whichever number is currently smaller.

How to solve Maximum Xor Product

Bits above n are fixed. Below n, matching bits can both become 1, and each mismatched bit lands in exactly one number — so the sum is fixed and the product is maximised by keeping the two numbers as balanced as possible.

Approach

  1. Walk i from n - 1 down to 0 with bit = 2^i.
  2. If a and b have the same value at bit, set it in both.
  3. Otherwise, if a > b (comparing the current values), make sure the bit ends up in b; else make sure it ends up in a — toggling both when it is on the wrong side (that is what XOR with x does).
  4. Return (a mod M) × (b mod M) mod M with M = 10^9 + 7, multiplying in 64 bits.

Why it works

Setting a matching bit raises both factors, so it can only help. For mismatched bits the total a' + b' is the same for every choice of x, and for a fixed sum the product grows as the factors get closer. Processing from the highest bit, the factor that is currently smaller stays smaller whatever lower bits do (a lower bit is worth less than a higher one), so handing it each mismatched bit is optimal; when the high parts tie, either choice gives the same product by symmetry.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Maximise the real product, then take the modulus — comparing products after mod picks the wrong x.
  • Reduce a and b modulo M before multiplying, and multiply in 64 bits: two values near 2^30 overflow 32-bit arithmetic.
  • With n = 0 the only choice is x = 0.

Reference solution

Python

def maximumXorProduct(a: int, b: int, n: int) -> int:
    for i in range(n - 1, -1, -1):
        bit = 1 << i
        if (a & bit) == (b & bit):
            a |= bit
            b |= bit
        elif a > b:
            if a & bit:
                a ^= bit
                b ^= bit
        else:
            if b & bit:
                a ^= bit
                b ^= bit
    return (a * b) % 1000000007

Java

public static int maximumXorProduct(int a, int b, int n) {
    for (int i = n - 1; i >= 0; i--) {
        int bit = 1 << i;
        if ((a & bit) == (b & bit)) { a |= bit; b |= bit; }
        else if (a > b) { if ((a & bit) != 0) { a ^= bit; b ^= bit; } }
        else { if ((b & bit) != 0) { a ^= bit; b ^= bit; } }
    }
    long M = 1000000007L;
    return (int) ((a % M) * (b % M) % M);
}

C++

int maximumXorProduct(int a, int b, int n) {
    for (int i = n - 1; i >= 0; i--) {
        int bit = 1 << i;
        if ((a & bit) == (b & bit)) { a |= bit; b |= bit; }
        else if (a > b) { if (a & bit) { a ^= bit; b ^= bit; } }
        else { if (b & bit) { a ^= bit; b ^= bit; } }
    }
    const long long M = 1000000007LL;
    return (int) ((a % M) * (b % M) % M);
}

JavaScript

var maximumXorProduct = function(a, b, n) {
    for (var i = n - 1; i >= 0; i--) {
        var bit = 1 << i;
        if ((a & bit) === (b & bit)) { a |= bit; b |= bit; }
        else if (a > b) { if (a & bit) { a ^= bit; b ^= bit; } }
        else { if (b & bit) { a ^= bit; b ^= bit; } }
    }
    var M = 1000000007;
    a %= M;
    b %= M;
    return ((a * (b >>> 16)) % M * 65536 + a * (b & 65535)) % M;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Greedy Algorithms · Bit Manipulation