Show problems as
Classic problem #2939MediumMathGreedyBit Manipulation

Maximum Xor Product

Real-world version: Toggled Register Product
Tracked in this browser only
Read Maximum Xor Product on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two meters hold the non-negative readings a and b. A calibration pulse is labelled by one non-negative integer x smaller than 2^n. Firing the pulse leaves each meter showing its own reading combined with x under bitwise exclusive-or. A pulse can therefore flip any chosen set of the n lowest bit positions, and it flips the very same positions in both meters.

Fire the pulse once, with x chosen freely in the range 0 <= x < 2^n. Among all allowed choices, take the largest product of the two resulting readings, reduce that product modulo 1000000007, and return the reduced value. The comparison that picks the largest uses the exact products, not the reduced ones.

Examples

Example 1

Input
a = 9, b = 6, n = 3
Output
56

The pulse may flip the three lowest bits. With `x = 1` the readings become `9 XOR 1 = 8` and `6 XOR 1 = 7`, and 8 * 7 = 56, which is smaller than the modulus and so is returned as it stands.

Example 2

Input
a = 12, b = 4, n = 2
Output
105

Only the two lowest bits may flip, so `x` is one of 0, 1, 2 and 3. With `x = 3` the readings become 15 and 7, whose product is 105.

Example 3

Input
a = 3, b = 3, n = 2
Output
9

Both readings are 3, so any pulse changes them identically. Leaving them alone with `x = 0` keeps the product at 9.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def maximum_xor_product(a: int, b: int, n: int) -> int:
Java
public int maximumXorProduct(long a, long b, int n)

More on the same topics