Jobs

Interviews

Discussions

Maximum Xor Product

Medium

Rippling

7 views

Topics:

Greedy AlgorithmsBit Manipulation

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

Since the answer may be too large, return it modulo 10⁹+ 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 < 2ⁿ.

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 < 2ⁿ.

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 < 2ⁿ.

Constraints:

0 <= a, b < 2⁵⁰
0 <= n <= 50

Maximum Xor Product

Medium

Rippling

7 views

Topics:

Greedy AlgorithmsBit Manipulation

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

Since the answer may be too large, return it modulo 10⁹+ 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 < 2ⁿ.

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 < 2ⁿ.

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 < 2ⁿ.

Constraints:

0 <= a, b < 2⁵⁰
0 <= n <= 50

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values of `a`, `b`, and `n`? Specifically, what are the maximum and minimum possible values for each?
Can `a` or `b` be negative initially?
If we don't use all `n` operations, is that acceptable?
Are we guaranteed that `a` and `b` are integers, or could they be floating-point numbers?
In the case of a tie (multiple ways to achieve the maximum product), is any valid product acceptable?

Brute Force Solution

Approach

The brute force strategy for the maximum XOR product problem involves checking all possible combinations of bit flips in the input numbers. For each possible combination, we compute the XOR product and then choose the combination that gives the largest XOR product. It's like trying out every single possibility to see which one works best.

Here's how the algorithm would work step-by-step:

Start with the original input numbers without flipping any bits.
Then, consider flipping one bit in the first number and see what XOR product we get.
Next, consider flipping one bit in the second number and compute the XOR product.
After that, look at flipping two bits: one in each number, and again check the XOR product.
Continue this process by flipping all the different possible combinations of bits in both numbers.
For every combination of flipped bits that you try, calculate the resulting XOR product of the modified numbers.
Compare all of the XOR products that you calculated, and keep track of the biggest one that you find.
After you have tried all possible combinations of bit flips, the largest XOR product you found is the answer.

Code Implementation

def maximum_xor_product_brute_force(first_number, second_number, maximum_bit_flips):
    maximum_xor_product = 0

    # Iterate through all possible combinations of bit flips
    for first_number_bit_flips in range(maximum_bit_flips + 1):
        for second_number_bit_flips in range(maximum_bit_flips - first_number_bit_flips + 1):
            
            #Try all combinations of flipping i bits in first_number and j bits in second_number
            for first_number_mask in range(1 << first_number_bit_flips):
                for second_number_mask in range(1 << second_number_bit_flips):
                    modified_first_number = first_number
                    modified_second_number = second_number

                    bit_counter = 0
                    temporary_mask = first_number_mask

                    # Flip the bits in the first number according to the mask
                    while temporary_mask > 0:
                        if temporary_mask & 1:
                            modified_first_number ^= (1 << bit_counter)
                        temporary_mask >>= 1
                        bit_counter += 1

                    bit_counter = 0
                    temporary_mask = second_number_mask

                    # Flip the bits in the second number according to the mask
                    while temporary_mask > 0:
                        if temporary_mask & 1:
                            modified_second_number ^= (1 << bit_counter)
                        temporary_mask >>= 1
                        bit_counter += 1

                    current_xor_product = (modified_first_number ^ modified_second_number)

                    # Update maximum if current product is larger
                    if current_xor_product > maximum_xor_product:
                        maximum_xor_product = current_xor_product

    return maximum_xor_product

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^(2n)) – Given two n-bit numbers, the brute force approach considers all possible combinations of bit flips for both numbers. For each number, there are 2^n possible bit flip combinations. Since we consider all combinations for both numbers, the total number of combinations is (2^n) * (2^n) = 2^(2n). For each combination, we calculate the XOR product in constant time, which doesn't affect the overall complexity. Thus, the time complexity is O(2^(2n)).

Space Complexity

O(1) – The brute force approach, as described, doesn't explicitly create any auxiliary data structures that scale with the input numbers. It operates by flipping bits and calculating XOR products, but it only needs to store a few variables to keep track of the current best product and potentially temporary copies of the numbers being manipulated. Therefore, the space used is constant and independent of the size of the input numbers, let's denote the size of the numbers as N (number of bits). This gives a space complexity of O(1).

Optimal Solution

Approach

The goal is to maximize the product of two XOR operations. The key insight is to manipulate the input numbers to make each XOR result as large as possible, prioritizing setting the most significant bits to 1. We achieve this by strategically adding or subtracting from the inputs based on the constraints.

Here's how the algorithm would work step-by-step:

First, figure out which numbers can be adjusted up or down based on the limit.
Then, check if we can make both XOR results large by increasing one number and decreasing the other.
If increasing one and decreasing the other doesn't work, try increasing both numbers, or decreasing both numbers, to maximize their XOR values.
For each possible adjustment (increasing, decreasing, or doing nothing), calculate the two XOR results and their product.
Finally, pick the adjustment strategy that gave you the biggest product of XOR values. If no adjustment is better, keep the original numbers.

Code Implementation

def maximum_xor_product(number_one, number_two, limit_a, limit_b):
    max_product = (number_one ^ number_two) * (number_one ^ number_two)
    number_one_increase = min(limit_a, number_one + (limit_a - number_one)) if number_one < limit_a else number_one
    number_one_decrease = max(0, number_one - number_one) if number_one > 0 else number_one
    number_two_increase = min(limit_b, number_two + (limit_b - number_two)) if number_two < limit_b else number_two
    number_two_decrease = max(0, number_two - number_two) if number_two > 0 else number_two

    # Try increasing number_one and decreasing number_two.
    if number_one < limit_a and number_two > 0:
        product = (number_one_increase ^ number_two_decrease) * (number_one_increase ^ number_two_decrease)
        max_product = max(max_product, product)

    # Try decreasing number_one and increasing number_two.
    if number_one > 0 and number_two < limit_b:
        product = (number_one_decrease ^ number_two_increase) * (number_one_decrease ^ number_two_increase)
        max_product = max(max_product, product)

    # Try increasing both numbers.
    if number_one < limit_a and number_two < limit_b:
        product = (number_one_increase ^ number_two_increase) * (number_one_increase ^ number_two_increase)
        max_product = max(max_product, product)

    # Try decreasing both numbers.
    if number_one > 0 and number_two > 0:
        product = (number_one_decrease ^ number_two_decrease) * (number_one_decrease ^ number_two_decrease)
        max_product = max(max_product, product)

    # Increasing only number_one.
    if number_one < limit_a:
        product = (number_one_increase ^ number_two) * (number_one_increase ^ number_two)
        max_product = max(max_product, product)

    # Decreasing only number one
    if number_one > 0:
        product = (number_one_decrease ^ number_two) * (number_one_decrease ^ number_two)
        max_product = max(max_product, product)

    # Increasing only number two
    if number_two < limit_b:
        product = (number_one ^ number_two_increase) * (number_one ^ number_two_increase)
        max_product = max(max_product, product)

    # Decreasing only number two
    if number_two > 0:
        product = (number_one ^ number_two_decrease) * (number_one ^ number_two_decrease)
        max_product = max(max_product, product)

    # We need to return the maximum value. 
    return max_product

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The algorithm explores a limited number of constant adjustments (increasing, decreasing, or doing nothing) to the input numbers A and B. For each adjustment, it calculates two XOR results and their product. Because the number of these adjustments and calculations is fixed regardless of the input values, the time complexity is constant. Therefore, the time complexity is O(1).

Space Complexity

O(1) – The algorithm's space complexity is primarily determined by the variables used to store the XOR results and their product for each adjustment strategy (increasing, decreasing, or no adjustment). Regardless of the input values or the limit, the number of these variables remains constant. No additional data structures like arrays or hash maps are created. Therefore, the auxiliary space used is constant, resulting in a space complexity of O(1).

Edge Cases

Case	How to Handle
n = 0	If n is zero, no operations are allowed, so return a * b modulo 10^9 + 7 directly.
a = 0 or b = 0	If a or b is initially zero, prioritize maximizing the other number to maximize the product.
a = b	If a equals b, try to maximize one and minimize the other within the constraints of n, since a large difference may yield a higher product.
Large a and b, close to 2^n - 1	Consider that XORing close to 2^n-1 value with x can decrease its value but might increase the other value more, affecting their product; handle accordingly with modular arithmetic to prevent overflow.
Large n, potential for many XOR operations	The number of possible XOR operations can be large, requiring careful decision-making regarding which number to XOR.
a and b are very small	If a and b are small, the objective would be to raise them to their maximum values possible using XOR.
Integer overflow during product calculation	Apply modulo 10^9 + 7 at each multiplication step to prevent integer overflow.
Negative a or b (or both)	Since the problem does not explicitly state that a and b are non-negative, treat a and b as signed integers, so we can choose to XOR a and b such that the result of the XOR becomes positive to improve the product.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values of `a`, `b`, and `n`? Specifically, what are the maximum and minimum possible values for each?
Can `a` or `b` be negative initially?
If we don't use all `n` operations, is that acceptable?
Are we guaranteed that `a` and `b` are integers, or could they be floating-point numbers?
In the case of a tie (multiple ways to achieve the maximum product), is any valid product acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the original input numbers without flipping any bits.
Then, consider flipping one bit in the first number and see what XOR product we get.
Next, consider flipping one bit in the second number and compute the XOR product.
After that, look at flipping two bits: one in each number, and again check the XOR product.
Continue this process by flipping all the different possible combinations of bits in both numbers.
For every combination of flipped bits that you try, calculate the resulting XOR product of the modified numbers.
Compare all of the XOR products that you calculated, and keep track of the biggest one that you find.
After you have tried all possible combinations of bit flips, the largest XOR product you found is the answer.

Code Implementation

def maximum_xor_product_brute_force(first_number, second_number, maximum_bit_flips):
    maximum_xor_product = 0

    # Iterate through all possible combinations of bit flips
    for first_number_bit_flips in range(maximum_bit_flips + 1):
        for second_number_bit_flips in range(maximum_bit_flips - first_number_bit_flips + 1):
            
            #Try all combinations of flipping i bits in first_number and j bits in second_number
            for first_number_mask in range(1 << first_number_bit_flips):
                for second_number_mask in range(1 << second_number_bit_flips):
                    modified_first_number = first_number
                    modified_second_number = second_number

                    bit_counter = 0
                    temporary_mask = first_number_mask

                    # Flip the bits in the first number according to the mask
                    while temporary_mask > 0:
                        if temporary_mask & 1:
                            modified_first_number ^= (1 << bit_counter)
                        temporary_mask >>= 1
                        bit_counter += 1

                    bit_counter = 0
                    temporary_mask = second_number_mask

                    # Flip the bits in the second number according to the mask
                    while temporary_mask > 0:
                        if temporary_mask & 1:
                            modified_second_number ^= (1 << bit_counter)
                        temporary_mask >>= 1
                        bit_counter += 1

                    current_xor_product = (modified_first_number ^ modified_second_number)

                    # Update maximum if current product is larger
                    if current_xor_product > maximum_xor_product:
                        maximum_xor_product = current_xor_product

    return maximum_xor_product

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out which numbers can be adjusted up or down based on the limit.
Then, check if we can make both XOR results large by increasing one number and decreasing the other.
If increasing one and decreasing the other doesn't work, try increasing both numbers, or decreasing both numbers, to maximize their XOR values.
For each possible adjustment (increasing, decreasing, or doing nothing), calculate the two XOR results and their product.
Finally, pick the adjustment strategy that gave you the biggest product of XOR values. If no adjustment is better, keep the original numbers.

Code Implementation

def maximum_xor_product(number_one, number_two, limit_a, limit_b):
    max_product = (number_one ^ number_two) * (number_one ^ number_two)
    number_one_increase = min(limit_a, number_one + (limit_a - number_one)) if number_one < limit_a else number_one
    number_one_decrease = max(0, number_one - number_one) if number_one > 0 else number_one
    number_two_increase = min(limit_b, number_two + (limit_b - number_two)) if number_two < limit_b else number_two
    number_two_decrease = max(0, number_two - number_two) if number_two > 0 else number_two

    # Try increasing number_one and decreasing number_two.
    if number_one < limit_a and number_two > 0:
        product = (number_one_increase ^ number_two_decrease) * (number_one_increase ^ number_two_decrease)
        max_product = max(max_product, product)

    # Try decreasing number_one and increasing number_two.
    if number_one > 0 and number_two < limit_b:
        product = (number_one_decrease ^ number_two_increase) * (number_one_decrease ^ number_two_increase)
        max_product = max(max_product, product)

    # Try increasing both numbers.
    if number_one < limit_a and number_two < limit_b:
        product = (number_one_increase ^ number_two_increase) * (number_one_increase ^ number_two_increase)
        max_product = max(max_product, product)

    # Try decreasing both numbers.
    if number_one > 0 and number_two > 0:
        product = (number_one_decrease ^ number_two_decrease) * (number_one_decrease ^ number_two_decrease)
        max_product = max(max_product, product)

    # Increasing only number_one.
    if number_one < limit_a:
        product = (number_one_increase ^ number_two) * (number_one_increase ^ number_two)
        max_product = max(max_product, product)

    # Decreasing only number one
    if number_one > 0:
        product = (number_one_decrease ^ number_two) * (number_one_decrease ^ number_two)
        max_product = max(max_product, product)

    # Increasing only number two
    if number_two < limit_b:
        product = (number_one ^ number_two_increase) * (number_one ^ number_two_increase)
        max_product = max(max_product, product)

    # Decreasing only number two
    if number_two > 0:
        product = (number_one ^ number_two_decrease) * (number_one ^ number_two_decrease)
        max_product = max(max_product, product)

    # We need to return the maximum value. 
    return max_product

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0	If n is zero, no operations are allowed, so return a * b modulo 10^9 + 7 directly.
a = 0 or b = 0	If a or b is initially zero, prioritize maximizing the other number to maximize the product.
a = b	If a equals b, try to maximize one and minimize the other within the constraints of n, since a large difference may yield a higher product.
Large a and b, close to 2^n - 1	Consider that XORing close to 2^n-1 value with x can decrease its value but might increase the other value more, affecting their product; handle accordingly with modular arithmetic to prevent overflow.
Large n, potential for many XOR operations	The number of possible XOR operations can be large, requiring careful decision-making regarding which number to XOR.
a and b are very small	If a and b are small, the objective would be to raise them to their maximum values possible using XOR.
Integer overflow during product calculation	Apply modulo 10^9 + 7 at each multiplication step to prevent integer overflow.
Negative a or b (or both)	Since the problem does not explicitly state that a and b are non-negative, treat a and b as signed integers, so we can choose to XOR a and b such that the result of the XOR becomes positive to improve the product.