Maximum XOR product of two numbers under one mask

Given integers a, b and n, choose x with 0 <= x < 2^n to maximize (a XOR x) * (b XOR x). Return the maximum modulo 10^9 + 7. Compare candidates by their true product, not by the product after the modulo.

Interface

Unless you agree on a different interface with the interviewer, assume:

• maximum_xor_product(a: int, b: int, n: int) -> int

Example

maximum_xor_product(12, 5, 4)  ->  98    # x = 2: 14 * 7
maximum_xor_product(6, 7, 5)   ->  930   # x = 25: 31 * 30
maximum_xor_product(1, 6, 3)   ->  12    # x = 5: 4 * 3

Constraints

• 0 <= a, b < 2^50
• 0 <= n <= 50

Clarifying questions

• Is the modulo applied only to the final answer?
• Can n be 0 (then x must be 0)?
• Can n be smaller than the bit length of a or b? (Yes: bits above n are fixed.)

What a strong answer covers

• Bits at positions >= n cannot change; keep them as they are in a and b.
• For each bit below n where a and b agree, set it to 1 in both results: it raises both factors.
• Where they differ, exactly one result gets the bit, so the sum is fixed. A product with a fixed sum is largest when the factors are as close as possible: go from the high bit down and give each differing bit to the factor that is currently smaller.
• The fixed bits above n count when deciding which factor is smaller; once one factor pulls ahead, every later differing bit goes to the other.
• O(n) time, O(1) space; Python integers or 64-bit math before the final modulo.
• A brute-force check over all x for small n as a test oracle.

Follow-ups

• Return the x that achieves the maximum (smallest one on ties).
• Maximize (a XOR x) + (b XOR x) instead; what changes?
• Three numbers a, b, c with the same x.