We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Xor Product

Number: 3192

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given three integers a, b, and n, you need to choose an integer x where 0 <= x < 2^n so that the expression (a XOR x) * (b XOR x) is maximized. Since the answer may be large, return the maximum value modulo 10^9 + 7. (Note: XOR denotes the bitwise exclusive or.)

Key Insights

  • Only the lower n bits of a and b are affected by choosing x (because 0 <= x < 2^n) while the higher bits remain constant.
  • By writing a = a_high2^n + a_low and b = b_high2^n + b_low (where a_low and b_low are the lower n bits), we have:
      a XOR x = a_high2^n + (a_low XOR x)
      b XOR x = b_high    2^n + (b_low XOR x)
  • Define U = a_low XOR x and observe that (b_low XOR x) can be written as U XOR c, where c = a_low XOR b_low.
  • The product becomes:
      (a_high2^n + U) * (b_high2^n + (U XOR c))
  • The only “free” part is choosing U (or equivalently x) in the range [0, 2^n). Therefore, the optimization reduces to choosing an n‑bit number U so that the resulting product (which also includes linear terms from the fixed higher bits) is maximized.
  • For the lower n bits, note that:
    • For any bit i where c has 0, both U and (U XOR c) have the same bit. Setting these bits to 1 increases both factors.
    • For any bit i where c has 1, the bits in U and (U XOR c) differ; to maximize the product it is best to “balance” the two factors (i.e. try to have numbers as equal as possible). We can do this greedily by processing from the most significant bit to the least significant bit and assigning the 1 to the factor that is smaller so far.
  • Finally, once we have computed the optimal U (denoted as u_opt) for the lower n bits, compute the full factors as:   factor1 = (a_high * 2^n) + u_opt
      factor2 = (b_high * 2^n) + (u_opt XOR c) and return (factor1 * factor2) % (10^9 + 7).

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We first split a and b into their higher parts (which remain unchanged when x only affects the lower n bits) and lower parts (which get XORed with x). By defining u = a_low XOR x and noting that b_low XOR x = u XOR (a_low XOR b_low), the problem reduces to choosing an n‑bit number u (denoted as u_opt) to maximize ( (a_high2^n + u) * (b_high2^n + (u XOR c)) ).

For each bit position i from n-1 downto 0:  • If the bit of c in that position is 0, we set the corresponding bit in both u_opt and (u_opt XOR c) to 1 (since adding a 1 to both numbers always increases the product).
 • If the bit of c is 1, then the two numbers will differ at that bit. To keep them as balanced as possible, we assign the 1 to the number which is currently smaller. When the two are equal we can choose arbitrarily (our implementation chooses to assign it to the second factor, though assigning to the first is equivalent). After computing u_opt this way, we obtain the full numbers by adding the fixed higher parts (multiplied by 2^n) back. The final answer is the product of these two numbers modulo 10^9+7.

Code Solutions

# Python solution with detailed line-by-line comments
MOD = 10**9 + 7

def maxXorProduct(a: int, b: int, n: int) -> int:
    # When n == 0, x can only be 0 so the answer is simply (a XOR 0) * (b XOR 0) = a * b
    if n == 0:
        return (a * b) % MOD

    # Split a and b into higher and lower parts (lower n bits)
    mask = (1 << n) - 1
    a_low = a & mask
    b_low = b & mask
    a_high = a >> n
    b_high = b >> n

    # c represents a_low XOR b_low
    c = a_low ^ b_low

    # u_opt will be the optimal value for a_low XOR x (i.e., our chosen u).
    u_opt = 0
    # v_opt is computed as u_opt XOR c (which equals b_low XOR x)
    v_opt = 0

    # Process bits from most significant (bit index n-1) to least significant (0)
    for i in range(n-1, -1, -1):
        bit_val = 1 << i  # current bit's value
        # Check the bit of c at position i
        if (c >> i) & 1 == 0:
            # When the bit in c is 0, bits in u and v are the same.
            # Set both bits to 1 since that always increases both numbers.
            u_opt |= bit_val
            v_opt |= bit_val
        else:
            # Bit in c is 1, so one of u and v gets the 1 and the other gets 0.
            # To balance the two numbers (and increase their product), assign 1 to the smaller number.
            if u_opt < v_opt:
                u_opt |= bit_val  # assign 1 to u_opt
                # v_opt remains unchanged (i.e., 0 at this bit)
            else:
                v_opt |= bit_val  # assign 1 to v_opt

    # Reconstruct the full numbers by adding the unchanged higher parts.
    factor1 = (a_high << n) + u_opt
    factor2 = (b_high << n) + (u_opt ^ c)  # (u_opt XOR c) equals the lower part for b XOR x

    # Return the product modulo 10^9+7.
    return (factor1 * factor2) % MOD

# Example usage:
print(maxXorProduct(12, 5, 4))  # Expected output: 98
print(maxXorProduct(6, 7, 5))   # Expected output: 930
print(maxXorProduct(1, 6, 3))   # Expected output: 12
← Back to All Questions