Skip to content

2939. Maximum Xor Product

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  int maximumXorProduct(long long a, long long b, int n) {
    constexpr int kMod = 1'000'000'007;
    if (n > 0)
      for (long bit = 1L << (n - 1); bit > 0; bit >>= 1)
        // Pick a bit if it makes min(a, b) larger.
        if ((min(a, b) & bit) == 0) {
          a ^= bit;
          b ^= bit;
        }
    return a % kMod * (b % kMod) % kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
  public int maximumXorProduct(long a, long b, int n) {
    final int MOD = 1_000_000_007;
    if (n > 0)
      for (long bit = 1L << (n - 1); bit > 0; bit >>= 1)
        // Pick a bit if it makes Math.min(a, b) larger.
        if ((Math.min(a, b) & bit) == 0) {
          a ^= bit;
          b ^= bit;
        }
    return (int) (a % MOD * (b % MOD) % MOD);
  }
}

1
2
3
4
5
6
7
8
9
class Solution:
  def maximumXorProduct(self, a: int, b: int, n: int) -> int:
    MOD = 1_000_000_007
    for bit in (2**i for i in range(n)):
      # Pick a bit if it makes min(a, b) larger.
      if a * b < (a ^ bit) * (b ^ bit):
        a ^= bit
        b ^= bit
    return a * b % MOD