2939. Maximum Xor Product LeetCode Solution

In this guide, you will get 2939. Maximum Xor Product LeetCode Solution with the best time and space complexity. The solution to Maximum Xor Product problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Xor Product solution in C++
Maximum Xor Product solution in Java
Maximum Xor Product solution in Python
Additional Resources

2939. Maximum Xor Product LeetCode Solution image

Problem Statement of Maximum Xor Product

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.

Example 1:

Input: a = 12, b = 5, n = 4
Output: 98
Explanation: For x = 2, (a XOR x) = 14 and (b XOR x) = 7. Hence, (a XOR x) * (b XOR x) = 98.
It can be shown that 98 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2n.

Example 2:

Input: a = 6, b = 7 , n = 5
Output: 930
Explanation: For x = 25, (a XOR x) = 31 and (b XOR x) = 30. Hence, (a XOR x) * (b XOR x) = 930.
It can be shown that 930 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2n.
Example 3:

Input: a = 1, b = 6, n = 3
Output: 12
Explanation: For x = 5, (a XOR x) = 4 and (b XOR x) = 3. Hence, (a XOR x) * (b XOR x) = 12.
It can be shown that 12 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2n.

Constraints:

0 <= a, b < 250
0 <= n <= 50

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

2939. Maximum Xor Product LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

2939. Maximum Xor Product LeetCode Solution in Java

class Solution {
  public int maximumXorProduct(long a, long b, int n) {
    final 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 Math.min(a, b) larger.
        if ((Math.min(a, b) & bit) == 0) {
          a ^= bit;
          b ^= bit;
        }
    return (int) (a % kMod * (b % kMod) % kMod);
  }
}
// code provided by PROGIEZ

2939. Maximum Xor Product LeetCode Solution in Python

class Solution:
  def maximumXorProduct(self, a: int, b: int, n: int) -> int:
    kMod = 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 % kMod
 # code by PROGIEZ