2939. Maximum Xor Product

MediumGreedyBit ManipulationMath
Leetcode Link

Problem Description

Given three integers a, b, and n, the task is to find the maximum value of (a XOR x) * (b XOR x) where x can be any integer from 0 to 2^n - 1 (both inclusive). Here, XOR refers to the bitwise exclusive OR operation. To ensure the return value is within a manageable size, we are asked to return the result after taking the modulo of 10^9 + 7.

We know that the XOR operation can flip bits in the binary representation of a number, depending on the bits of another number it is being XORed with. The catch here is to intelligently select the value of x that, when XORed with a and b, results in the maximum possible product (a XOR x) * (b XOR x).

Intuition

The solution follows a greedy approach combined with bitwise operations. The intuition behind the solution lies in understanding how the XOR operation affects the bits of the operands and consequently, the product of the two results. The XOR operation with 1 flips a bit, while XOR with 0 leaves it unchanged. The goal is to carefully set each bit of x to either 0 or 1 in such a way that the resulting product is maximized.

The process starts with ensuring that the most significant bits (those beyond n) of a and b are preserved as they will always contribute to the larger value in the product when XORed with 0. These parts are denoted as ax and bx respectively.

Then, for each bit from the most significant bit n-1 to the least significant bit 0, we decide whether to set the corresponding bit in ax and bx to 1. If the current bits of a and b are equal, setting the bit to 1 in both ax and bx does not change their product, but as these bits are less significant than the preserved parts, it is optimal to set them to 1.

However, when the bits of a and b are different, we have a decision to make. To increase the product, we want to flip the bit of the smaller operand among ax and bx. This way, we are increasing the smaller number without decreasing the other, thus maximizing the product.

By iterating from the most significant bit to the least significant bit in this manner and updating ax and bx accordingly, we ensure that we arrive at the highest possible product. Once we have determined the optimal ax and bx, the final result is their product, modulo 10^9 + 7.

Learn more about Greedy and Math patterns.

Solution Approach

The solution approach makes clever use of bitwise operations to arrive at the maximum product. Here's how the algorithm proceeds:

  1. The first step is to preserve the bits of a and b that are above the n-th bit since those are not affected by XOR with any x in the given range 0 to 2^n - 1.

    • This is done by right-shifting a and b by n and then left-shifting back by n. The result is stored in two new variables ax and bx. This effectively zeroes out the bits in positions 0 to n-1 since right-shifting followed by left-shifting with the same number of bits fills the vacated bits with zeroes.
  2. The core of the algorithm then iterates over each bit position from n-1 down to 0:

    • For each bit position i, we extract the bit value of a and b at position i using the bitwise AND operation with 1 << i.
    • Next, we determine if the current bits of a and b, letā€™s call them x and y, are the same or not. If they are the same, then regardless of what value x takes for bit position i, the product will be maximized if the bit position i is set to 1 for both ax and bx.
  3. However, if x and y are not equal, we compare the values of ax and bx. We only want to flip the bit of the smaller value between the two:

    • If ax is greater than bx, then we increase bx by setting its i-th bit to ensure bx is increased.
    • Conversely, if bx is greater or equal to ax, then we increase ax by setting its i-th bit.
    • This operation intends to make bx and ax more equal in value, as the maximum product of two numbers happens when they are closest to each other in value.
  4. After determining the optimal ax and bx, we calculate the product and take the modulo with 10^9 + 7 to get the final result:

    • ax * bx % mod

Each of these steps complies with the greedy paradigm of algorithm design, as we are making the locally optimal choice of setting bit i in hope of finding the global maximum product. By considering bit positions in a descending order, we prioritize the influence of higher-order bits on the product, which is key since they contribute significantly more to the value than lower-order bits.

In terms of data structures, no additional structures are necessary; the solution uses basic integer variables to store the modified versions of a and b, as well as to handle intermediate values as we iterate over the bits.

By breaking down the bitwise operations and decision-making process, we can see exactly how the algorithm maximizes the final product and ensure that it conforms to the constraints and requirements described in the problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Assume we are given a = 22, b = 27, and n = 5. The binary representations of a and b within 5 bits are 10110 for a and 11011 for b. We aim to find an x such that (a XOR x) * (b XOR x) is maximized, where x ranges from 0 to 2^5 - 1, i.e., 0 to 31.

Step 1: Since n equals 5, we do not need to alter a and b for this particular example because any x within the range will not affect bits beyond the 5th bit.

Step 2: We start iterating from the 4th bit (most significant bit) to the 0th bit (least significant bit):

For the 4th bit (2^4 or 16 place):

  • a at 4th bit is 1, b at 4th bit is 1. Both are the same. We choose x to have 0 at this bit to keep the bits intact and maintain the high value.

For the 3rd bit (2^3 or 8 place):

  • a at 3rd bit is 0, b at 3rd bit is 1. They differ. We want to flip the bit for the smaller operand of the two (for our purposes, since their bits beyond n are zero, ax and bx correspond to a and b). So x will have 1 at this bit to flip a's 3rd bit and make it larger.

For the 2nd bit (2^2 or 4 place):

  • Both a and b have 1 at this bit. No changes needed; we choose x to have 0 at this bit.

For the 1st bit (2^1 or 2 place):

  • a at 1st bit is 1, b at 1st bit is 0. They are different again, and b is smaller at the 1st bit. We choose x to have 1 at this bit to flip b's 1st bit.

For the 0th bit (2^0 or 1 place):

  • a at 0th bit is 0, b at 0th bit is 1. We flip a's 0th bit by choosing x to have 1 at this bit.

Based on the decisions above, for each bit, x will be 01111 in binary or 15 in decimal.

Step 3: Now we compute (a XOR x) * (b XOR x):

  • (a XOR x) in binary: 10110 XOR 01111 equals 11001 (decimal 25)
  • (b XOR x) in binary: 11011 XOR 01111 equals 10100 (decimal 20)

Step 4: The product is 25 * 20 = 500. The modulo operation is not needed in this specific case because the product is already less than 10^9 + 7.

Thus, the maximum value for (a XOR x) * (b XOR x) is 500 for x = 15.

This example demonstrates the step-by-step process described in the solution approach by carefully constructing the optimal value of x using bitwise operations to maximize the product.

Solution Implementation

1class Solution:
2    def maximum_xor_product(self, num1: int, num2: int, num_bits: int) -> int:
3        # Define the modulus for taking the result % mod
4        MODULUS = 10**9 + 7
5
6        # Initialize variables to store the maximum XOR values based on the most significant bits
7        xor_num1, xor_num2 = (num1 >> num_bits) << num_bits, (num2 >> num_bits) << num_bits
8
9        # Iterate over each bit, from most significant bit to least significant bit
10        for i in range(num_bits - 1, -1, -1):
11            # Extract the current bit of num1 and num2
12            bit_num1 = (num1 >> i) & 1
13            bit_num2 = (num2 >> i) & 1
14
15            # If the current bits are equal, set the current bit in both xor_num1 and xor_num2
16            if bit_num1 == bit_num2:
17                xor_num1 |= 1 << i
18                xor_num2 |= 1 << i
19            # If xor_num1 is greater, set the current bit in xor_num2
20            elif xor_num1 > xor_num2:
21                xor_num2 |= 1 << i
22            # Otherwise, set the current bit in xor_num1
23            else:
24                xor_num1 |= 1 << i
25
26        # Return the product of xor_num1 and xor_num2 modulo MODULUS
27        return (xor_num1 * xor_num2) % MODULUS
28
1class Solution {
2    public int maximumXorProduct(long num1, long num2, int bits) {
3        final int MODULUS = (int) 1e9 + 7; // The modulus value for the result
4      
5        // These two variables represent num1 and num2 with the last 'bits' bits set to 0
6        long adjustedNum1 = (num1 >> bits) << bits;
7        long adjustedNum2 = (num2 >> bits) << bits;
8      
9        // Iterate over each bit from 'bits-1' down to 0
10        for (int i = bits - 1; i >= 0; --i) {
11            long bitNum1 = (num1 >> i) & 1; // Get the ith bit of num1
12            long bitNum2 = (num2 >> i) & 1; // Get the ith bit of num2
13          
14            // If ith bits of num1 and num2 are equal, set ith bits of adjustedNum1 and adjustedNum2 to 1
15            if (bitNum1 == bitNum2) {
16                adjustedNum1 |= 1L << i;
17                adjustedNum2 |= 1L << i;
18            } 
19            // Otherwise, if adjustedNum1 is less than adjustedNum2, set ith bit of adjustedNum1 to 1
20            else if (adjustedNum1 < adjustedNum2) {
21                adjustedNum1 |= 1L << i;
22            } 
23            // Otherwise, set ith bit of adjustedNum2 to 1
24            else {
25                adjustedNum2 |= 1L << i;
26            }
27        }
28      
29        // Apply modulus operation to both adjusted numbers to ensure the product is within the range
30        adjustedNum1 %= MODULUS;
31        adjustedNum2 %= MODULUS;
32      
33        // Calculate the product of adjustedNum1 and adjustedNum2, apply modulus operation, and cast to integer
34        return (int) (adjustedNum1 * adjustedNum2 % MODULUS);
35    }
36}
37
1class Solution {
2public:
3    int maximumXorProduct(long long numA, long long numB, int n) {
4        const int MOD = 1e9 + 7; // Define the modulo constant for the result
5
6        // Initialize `aXor` and `bXor` by preserving the higher bits up to `n` and setting lower bits to 0
7        long long aXor = (numA >> n) << n;
8        long long bXor = (numB >> n) << n;
9
10        // Iterate bit positions from n-1 down to 0
11        for (int bitPos = n - 1; bitPos >= 0; --bitPos) {
12            // Extract the bit at `bitPos` for both `numA` and `numB`
13            int bitA = (numA >> bitPos) & 1;
14            int bitB = (numB >> bitPos) & 1;
15
16            // If the bits are the same, set the bit at `bitPos` in both `aXor` and `bXor`
17            if (bitA == bitB) {
18                aXor |= 1LL << bitPos;
19                bXor |= 1LL << bitPos;
20            } else if (aXor < bXor) {
21                // If `aXor` is less than `bXor`, set the bit in `aXor`
22                aXor |= 1LL << bitPos;
23            } else {
24                // Otherwise, set the bit in `bXor`
25                bXor |= 1LL << bitPos;
26            }
27        }
28
29        // Apply the modulo operation to both `aXor` and `bXor`
30        aXor %= MOD;
31        bXor %= MOD;
32
33        // Return the product of `aXor` and `bXor` under modulo
34        return (aXor * bXor) % MOD;
35    }
36};
37
1function maximumXorProduct(a: number, b: number, n: number): number {
2    // Define the modulus for the final result to avoid large numbers
3    const MOD = BigInt(1e9 + 7);
4
5    // Initialize ax and bx to only include the bits from a and b above the nth bit
6    // This effectively zeroes out the last n bits
7    let ax = (BigInt(a) >> BigInt(n)) << BigInt(n);
8    let bx = (BigInt(b) >> BigInt(n)) << BigInt(n);
9
10    // Loop over each bit from n-1 down to 0
11    for (let i = BigInt(n - 1); i >= 0; --i) {
12        // Extract the ith bit from both a and b
13        const aBit = (BigInt(a) >> i) & 1n;
14        const bBit = (BigInt(b) >> i) & 1n;
15
16        // If the bits are equal, set the ith bit of both ax and bx
17        if (aBit === bBit) {
18            ax |= 1n << i;
19            bx |= 1n << i;
20        }
21        // If ax is currently less than bx, set the ith bit of ax
22        else if (ax < bx) {
23            ax |= 1n << i;
24        }
25        // Otherwise, set the ith bit of bx
26        else {
27            bx |= 1n << i;
28        }
29    }
30
31    // Reduce ax and bx by the modulus to handle overflow
32    ax %= MOD;
33    bx %= MOD;
34
35    // Calculate the product of ax and bx, reduce it by the modulus, 
36    // and return the number representation of the result
37    return Number((ax * bx) % MOD);
38}
39

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n). Here, n refers to the value given as an argument to the function, not the size of any input array or list, as might typically be the case in algorithmic problems. The code iterates from n - 1 down to 0 via the for loop, resulting in exactly n iterations, hence the time complexity is linear with respect to n.

Space Complexity

The space complexity of the code is O(1). This analysis is straightforward as the function operates in constant space, using a fixed number of integer variables (mod, ax, bx, i, x, y) regardless of the value of n or the size of the input numbers a and b. There are no data structures used that grow with the size of the input, which confirms that the space requirements remain constant.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More