Problem Description

You are given three integers a, b, and n. Your task is to find a value x where 0 <= x < 2^n that maximizes the expression (a XOR x) * (b XOR x).

The XOR operation is the bitwise exclusive OR operation. Since the result can be very large, you need to return the answer modulo 10^9 + 7.

The key insight is that x can only affect the lower n bits of both a and b. Any bits at position n or higher in a and b remain unchanged regardless of the value of x.

The solution works by greedily choosing bits for x from the most significant bit (position n-1) down to the least significant bit (position 0). For each bit position i:

• If both a and b have the same bit value at position i, setting the corresponding bit in x to the opposite value will make both results have a 1 at that position after XOR, maximizing the product.
• If a and b have different bit values at position i, exactly one of them will have a 1 at that position after XOR. The algorithm chooses to give the 1 to whichever value (ax or bx) is currently smaller to balance them and maximize their product.

The algorithm maintains ax and bx which represent (a XOR x) and (b XOR x) respectively, building them up bit by bit based on the greedy choices made for each bit position.

Intuition

To maximize the product (a XOR x) * (b XOR x), we need to think about how XOR operations work and how to make both resulting values as large as possible.

First, notice that x can only be in the range [0, 2^n), which means x can only have bits set in positions 0 to n-1. Any bits at position n or higher in a and b won't be affected by XORing with x.

For any bit position i (where i < n), we can choose whether to set that bit in x to 0 or 1. This choice affects the i-th bit in both (a XOR x) and (b XOR x):

• If a has bit i as 0 and we set x's bit i to 1, then (a XOR x) will have bit i as 1
• If a has bit i as 1 and we set x's bit i to 1, then (a XOR x) will have bit i as 0

The key insight is that when both a and b have the same bit value at position i, we can make both results have a 1 at that position by choosing the appropriate bit value for x. This is always beneficial since having 1s in higher bit positions increases the values more significantly.

When a and b have different bit values at position i, only one of them can have a 1 at that position in the final result. Here, we face a choice: which one should get the 1? The greedy strategy is to give the 1 to whichever value is currently smaller. This helps balance the two values, and for multiplication, having two balanced values generally gives a larger product than having one very large and one very small value (think of how 5 * 5 = 25 is larger than 9 * 1 = 9 even though the sum is the same).

By processing bits from most significant to least significant, we ensure that our decisions for higher-value bits take priority, as they have a greater impact on the final product.

Learn more about Greedy and Math patterns.

Solution Approach

The implementation follows a greedy approach, processing bits from position n-1 down to 0:

1. Extract the unchangeable parts: First, we extract the bits at positions n and higher from both a and b, since these cannot be affected by x. We do this by:

   • ax = (a >> n) << n - shifts a right by n bits to remove lower bits, then shifts back left to get only the higher bits
   • bx = (b >> n) << n - same operation for b

2. Process each bit position from high to low: We iterate through bit positions from n-1 down to 0:

   for i in range(n - 1, -1, -1):

3. Extract current bit values: For each position i, we check the bit values in the original a and b:

   • x = a >> i & 1 - gets the i-th bit of a
   • y = b >> i & 1 - gets the i-th bit of b

4. Apply the greedy strategy:

   • Case 1: Same bits (x == y): If both have the same bit value, we can make both results have a 1 at position i by choosing the opposite bit for x. We set the i-th bit to 1 in both ax and bx:

     ax |= 1 << i
     bx |= 1 << i

   • Case 2: Different bits (x != y): Only one result can have a 1 at position i. We give it to the currently smaller value to balance them:

     elif ax > bx:
         bx |= 1 << i  # Give the 1 to bx since it's smaller
     else:
         ax |= 1 << i  # Give the 1 to ax since it's smaller or equal

5. Return the result: Finally, we compute the product ax * bx and return it modulo 10^9 + 7:

   return ax * bx % mod

The time complexity is O(n) since we process each of the n bits once. The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through an example with a = 12, b = 5, and n = 4.

Initial Setup:

• a = 12 in binary: 1100
• b = 5 in binary: 0101
• We need to find x where 0 ≤ x < 16 (since 2^4 = 16)

Step 1: Extract unchangeable parts Since n = 4, we need bits at position 4 and higher:

• ax = (12 >> 4) << 4 = 0 (no bits at position 4 or higher)
• bx = (5 >> 4) << 4 = 0 (no bits at position 4 or higher)

Step 2: Process each bit from position 3 to 0

Bit position 3:

• Bit in a: (12 >> 3) & 1 = 1
• Bit in b: (5 >> 3) & 1 = 0
• Since bits are different, only one can have a 1 after XOR
• Currently ax = 0 and bx = 0 (equal), so we give the 1 to ax
• ax = 0 | (1 << 3) = 8, bx = 0

Bit position 2:

• Bit in a: (12 >> 2) & 1 = 1
• Bit in b: (5 >> 2) & 1 = 1
• Since bits are the same, we can make both have 1 by choosing opposite in x
• ax = 8 | (1 << 2) = 12, bx = 0 | (1 << 2) = 4

Bit position 1:

• Bit in a: (12 >> 1) & 1 = 0
• Bit in b: (5 >> 1) & 1 = 0
• Since bits are the same, we can make both have 1 by choosing opposite in x
• ax = 12 | (1 << 1) = 14, bx = 4 | (1 << 1) = 6

Bit position 0:

• Bit in a: (12 >> 0) & 1 = 0
• Bit in b: (5 >> 0) & 1 = 1
• Since bits are different, only one can have a 1 after XOR
• Currently ax = 14 and bx = 6 (ax > bx), so we give the 1 to bx
• ax = 14, bx = 6 | (1 << 0) = 7

Final Result:

• ax = 14, bx = 7
• Product = 14 * 7 = 98

To verify, we can reconstruct x:

• At position 3: we chose to make a XOR x have 1, so x bit 3 = opposite of a bit 3 = 0
• At position 2: we chose to make both have 1, so x bit 2 = opposite of their common bit = 0
• At position 1: we chose to make both have 1, so x bit 1 = opposite of their common bit = 1
• At position 0: we chose to make b XOR x have 1, so x bit 0 = opposite of b bit 0 = 0

Therefore, x = 0010 (binary) = 2 (decimal)

Verification: (12 XOR 2) * (5 XOR 2) = 14 * 7 = 98 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through a loop from n-1 down to 0, performing constant-time operations in each iteration. The loop runs exactly n times, where each iteration involves:

• Bit extraction operations (a >> i & 1 and b >> i & 1): O(1)
• Comparison operations: O(1)
• Bitwise OR operations to set bits: O(1)

The initial operations before the loop (computing ax and bx using bit shifts) are also O(1) operations. The final multiplication and modulo operation at the end is O(1). Therefore, the overall time complexity is O(n).

Space Complexity: O(1)

The algorithm uses only a fixed amount of extra space:

• Variables mod, ax, bx: constant space
• Loop variable i: constant space
• Temporary variables x and y for bit values: constant space

No additional data structures that grow with input size are used. The space usage remains constant regardless of the value of n, resulting in O(1) space complexity.

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

Common Pitfalls

1. Incorrect Bit Extraction for High Bits

A common mistake is incorrectly preserving the bits at position n and above. Some might try:

# WRONG: This doesn't preserve high bits correctly
ax = a & ~((1 << n) - 1)  # Might overflow for large n

Issue: Using bit masks with large values of n can cause issues, and the logic can be confusing.

Solution: Use the shift operations as shown in the correct implementation:

ax = (a >> n) << n  # Clearly removes lower n bits then restores position
bx = (b >> n) << n

2. Forgetting the Modulo Operation

The result can be extremely large, and forgetting to apply modulo can cause:

• Integer overflow in languages with fixed integer sizes
• Wrong answer on the platform

# WRONG: Missing modulo
return ax * bx

# CORRECT: Apply modulo
return (ax * bx) % MOD

3. Incorrect Greedy Decision for Different Bits

When bits differ, a common mistake is always giving the bit to a specific number or using the wrong comparison:

# WRONG: Always favor ax regardless of current values
if bit_a != bit_b:
    ax |= (1 << i)

# WRONG: Compare original a and b instead of current ax and bx
if bit_a != bit_b:
    if a > b:  # Should be ax > bx
        bx |= (1 << i)
    else:
        ax |= (1 << i)

Solution: Compare the current accumulated values ax and bx:

if ax > bx:
    bx |= (1 << i)
else:
    ax |= (1 << i)

4. Off-by-One Error in Bit Range

Processing the wrong range of bits is a common error:

# WRONG: Processes n bits instead of n-1 to 0
for i in range(n, 0, -1):  # Goes from n to 1

# CORRECT: Process bits from position n-1 down to 0
for i in range(n - 1, -1, -1):  # Goes from n-1 to 0

5. Not Understanding XOR Properties

Some might try complex calculations instead of using the simple property that a XOR x at bit i equals:

• 1 if a[i] != x[i]
• 0 if a[i] == x[i]

This leads to unnecessarily complex code when the greedy approach is straightforward:

• If a[i] == b[i], choose x[i] to be opposite to maximize both
• If a[i] != b[i], one will be 1 and one will be 0 regardless, so balance the values