2939

2939. Maximum Xor Product (Medium)

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

Related Topics:
Math, Greedy, Bit Manipulation

Similar Questions:

• Maximum XOR After Operations (Medium)

Hints:

• Iterate over bits from most significant to least significant.
• For the ith bit, if both a and b have the same value, we can always make x’s ith bit different from a and b, so a ^ x and b ^ x both have the ith bit set.
• Otherwise, we can only set the ith bit of one of a ^ x or b ^ x. Depending on the previous bits of a ^ x or b ^ x, we should set the smaller value’s ith bit.

Solution 1.

// OJ: https://leetcode.com/problems/maximum-xor-product
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/maximum-xor-product/solutions/4304377/no-multiplication/
class Solution {
public:
    int maximumXorProduct(long long a, long long b, int n) {
        int mod = 1e9 + 7;
        if (n) {
            for (long long bt = 1LL << (n - 1); bt > 0; bt >>= 1) {
                if ((min(a, b) & bt) == 0) {
                    a ^= bt;
                    b ^= bt;
                }
            }
        }
        return a % mod * (b % mod) % mod;
    }
};