Problem

Given three integers a, b, and n, return themaximum value of (a XOR x) * (b XOR x) where 0 <= x < 2n.

Since the answer may be too large, return it modulo 10^9 + 7.

Note that XOR is the bitwise XOR operation.

Examples

Example 1

1
2
3
4
5
6
7
8


    
    
    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

1
2
3
4
5
6
7


    
    
    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

1
2
3
4
5
6
7
8


    
    
    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

Solution

Method 1 – Bitwise Greedy Maximization

Intuition

To maximize (a XOR x) * (b XOR x), we want both terms to be as large as possible. Since XOR flips bits, setting bits in x where a and b have zeros can help maximize both terms. The largest possible value for x is 2^n - 1, which sets all n bits to 1.

Approach

  1. Compute limit = (1 << n) - 1 (all n bits set).
  2. Try x = limit and check the product.
  3. Try all possible x in [0, limit] (brute force, since n is small).
  4. Track the maximum product modulo 10^9 + 7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int maximumXorProduct(int a, int b, int n) {
        int mod = 1e9 + 7;
        int lim = (1 << n) - 1;
        long long ans = 0;
        for (int x = 0; x <= lim; ++x) {
            long long cur = 1LL * (a ^ x) * (b ^ x);
            if (cur > ans) ans = cur;
        }
        return ans % mod;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func maximumXorProduct(a int, b int, n int) int {
    mod := int(1e9 + 7)
    lim := (1 << n) - 1
    ans := 0
    for x := 0; x <= lim; x++ {
        cur := (a ^ x) * (b ^ x)
        if cur > ans {
            ans = cur
        }
    }
    return ans % mod
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int maximumXorProduct(int a, int b, int n) {
        int mod = 1000000007;
        int lim = (1 << n) - 1;
        long ans = 0;
        for (int x = 0; x <= lim; x++) {
            long cur = (long)(a ^ x) * (b ^ x);
            if (cur > ans) ans = cur;
        }
        return (int)(ans % mod);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun maximumXorProduct(a: Int, b: Int, n: Int): Int {
        val mod = 1000000007
        val lim = (1 shl n) - 1
        var ans = 0L
        for (x in 0..lim) {
            val cur = (a xor x).toLong() * (b xor x)
            if (cur > ans) ans = cur
        }
        return (ans % mod).toInt()
    }
}
1
2
3
4
5
6
7
8
9

def maximum_xor_product(a: int, b: int, n: int) -> int:
    mod = 10**9 + 7
    lim = (1 << n) - 1
    ans = 0
    for x in range(lim + 1):
        cur = (a ^ x) * (b ^ x)
        if cur > ans:
            ans = cur
    return ans % mod
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn maximum_xor_product(a: i32, b: i32, n: i32) -> i32 {
        let modv = 1_000_000_007;
        let lim = (1 << n) - 1;
        let mut ans = 0i64;
        for x in 0..=lim {
            let cur = ((a ^ x) as i64) * ((b ^ x) as i64);
            if cur > ans { ans = cur; }
        }
        (ans % modv) as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    maximumXorProduct(a: number, b: number, n: number): number {
        const mod = 1e9 + 7;
        const lim = (1 << n) - 1;
        let ans = 0;
        for (let x = 0; x <= lim; ++x) {
            const cur = (a ^ x) * (b ^ x);
            if (cur > ans) ans = cur;
        }
        return ans % mod;
    }
}

Complexity

  • ⏰ Time complexity: O(2^n), since we try all possible x in [0, 2^n - 1].
  • 🧺 Space complexity: O(1), only a few variables are used for computation.