0612MediumMathGreedyBit Manipulation

Toggled Register Product

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

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

Java

public int maximumXorProduct(long a, long b, int n)

The intended approach

Time O(n) — one pass over the n adjustable bit positions.Space O(1) — a fixed number of integers.

The two resulting readings are assembled from the most significant bit downwards. Bit positions from `n` upwards are outside the pulse's reach and are copied straight across. For a position below `n` where the two input bits are the same, one choice puts a 1 there in both results, which raises both factors by the same amount. For a position where the input bits differ, exactly one of the two results gets the 1, so the sum of the results is fixed and the choice only shifts the balance; the code hands the 1 to whichever partial result is currently smaller. Both factors are reduced modulo 1000000007 only at the very end, so the comparisons all use exact values.

Pythonentry point: maximum_xor_product

def maximum_xor_product(a, b, n):
    # O(n) time, O(1) space. Build the two resulting readings bit by bit from
    # the top. Bits at or above position n cannot change, so they are copied
    # over first. Below that, a position where the two readings agree can be
    # driven to 1 in both at no cost to either. A position where they disagree
    # hands its 1 to exactly one of the two, and the bits still undecided are
    # worth less together than the current position, so the decision is made
    # on the partial readings built so far.
    MOD = 1000000007
    keep = ~((1 << n) - 1)
    first = a & keep
    second = b & keep
    for i in range(n - 1, -1, -1):
        bit_a = (a >> i) & 1
        bit_b = (b >> i) & 1
        if bit_a == bit_b:
            first |= 1 << i
            second |= 1 << i
        elif first <= second:
            first |= 1 << i
        else:
            second |= 1 << i
    return (first % MOD) * (second % MOD) % MOD

The obvious version

Try every pulse value in the range, compute the exact product of the two resulting readings for each one, keep the largest, and reduce it modulo 1000000007 at the end.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_maximum_xor_product(a, b, n):
    best = 0
    for x in range(1 << n):
        product = (a ^ x) * (b ^ x)
        if product > best:
            best = product
    return best % 1000000007

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in