Welcome to Subscribe On Youtube

2939. Maximum Xor Product

Description

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

Solutions

Solution 1: Greedy + Bitwise Operation

According to the problem description, we can assign a number to the [0..n) bits of a and b in binary at the same time, so that the product of a and b is maximized.

Therefore, we first extract the parts of a and b that are higher than the n bits, denoted as ax and bx.

Next, we consider each bit in [0..n) from high to low. We denote the current bits of a and b as x and y.

If x=y, then we can set the current bit of ax and bx to 1 at the same time. Therefore, we update ax=ax1«i and bx=bx1«i. Otherwise, if ax<bx, to maximize the final product, we should set the current bit of ax to 1. Otherwise, we can set the current bit of bx to 1.

Finally, we return ax×bxmod(109+7) as the answer.

The time complexity is O(n), where n is the integer given in the problem. The space complexity is O(1).

  • class Solution {
        public int maximumXorProduct(long a, long b, int n) {
            final int mod = (int) 1e9 + 7;
            long ax = (a >> n) << n;
            long bx = (b >> n) << n;
            for (int i = n - 1; i >= 0; --i) {
                long x = a >> i & 1;
                long y = b >> i & 1;
                if (x == y) {
                    ax |= 1L << i;
                    bx |= 1L << i;
                } else if (ax < bx) {
                    ax |= 1L << i;
                } else {
                    bx |= 1L << i;
                }
            }
            ax %= mod;
            bx %= mod;
            return (int) (ax * bx % mod);
        }
    }
    
  • class Solution {
    public:
        int maximumXorProduct(long long a, long long b, int n) {
            const int mod = 1e9 + 7;
            long long ax = (a >> n) << n, bx = (b >> n) << n;
            for (int i = n - 1; ~i; --i) {
                int x = a >> i & 1, y = b >> i & 1;
                if (x == y) {
                    ax |= 1LL << i;
                    bx |= 1LL << i;
                } else if (ax < bx) {
                    ax |= 1LL << i;
                } else {
                    bx |= 1LL << i;
                }
            }
            ax %= mod;
            bx %= mod;
            return ax * bx % mod;
        }
    };
    
  • class Solution:
        def maximumXorProduct(self, a: int, b: int, n: int) -> int:
            mod = 10**9 + 7
            ax, bx = (a >> n) << n, (b >> n) << n
            for i in range(n - 1, -1, -1):
                x = a >> i & 1
                y = b >> i & 1
                if x == y:
                    ax |= 1 << i
                    bx |= 1 << i
                elif ax > bx:
                    bx |= 1 << i
                else:
                    ax |= 1 << i
            return ax * bx % mod
    
    
  • func maximumXorProduct(a int64, b int64, n int) int {
    	const mod int64 = 1e9 + 7
    	ax := (a >> n) << n
    	bx := (b >> n) << n
    	for i := n - 1; i >= 0; i-- {
    		x, y := (a>>i)&1, (b>>i)&1
    		if x == y {
    			ax |= 1 << i
    			bx |= 1 << i
    		} else if ax < bx {
    			ax |= 1 << i
    		} else {
    			bx |= 1 << i
    		}
    	}
    	ax %= mod
    	bx %= mod
    	return int(ax * bx % mod)
    }
    
  • function maximumXorProduct(a: number, b: number, n: number): number {
        const mod = BigInt(1e9 + 7);
        let ax = (BigInt(a) >> BigInt(n)) << BigInt(n);
        let bx = (BigInt(b) >> BigInt(n)) << BigInt(n);
        for (let i = BigInt(n - 1); ~i; --i) {
            const x = (BigInt(a) >> i) & 1n;
            const y = (BigInt(b) >> i) & 1n;
            if (x === y) {
                ax |= 1n << i;
                bx |= 1n << i;
            } else if (ax < bx) {
                ax |= 1n << i;
            } else {
                bx |= 1n << i;
            }
        }
        ax %= mod;
        bx %= mod;
        return Number((ax * bx) % mod);
    }
    
    

All Problems

All Solutions