1124MediumGreedyBit Manipulation

Matching the Notch Count as Closely as You Can

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 whole numbers num1 and num2 are given. Build a whole number x carrying exactly as many 1 bits as num2 does, chosen so that the bitwise exclusive-or of x and num1 comes out as small as possible.

Return x. Exactly one number meets both demands.

Examples

Example 1

Input: num1 = 8, num2 = 3
Output: 9

Two bits are allowed. Keeping the bit num1 already carries costs nothing, and the cheapest home for the second is the lowest free place.

Example 2

Input: num1 = 15, num2 = 1
Output: 8

Only one bit is allowed, so three of num1's four bits have to go. Dropping the highest would cost more than dropping all the others, so that is the one kept.

Example 3

Input: num1 = 1, num2 = 15
Output: 15

Four bits are needed and num1 supplies one of them. The other three take the lowest free places, which is the smallest number with four bits.

Constraints

1 <= num1 <= 10^9
1 <= num2 <= 10^9

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 minimize_xor(num1: int, num2: int) -> int:

Java

public int minimizeXor(int num1, int num2)

The intended approach

Time O(b) over the bit places.Space O(1).

The exclusive-or carries a `1` at every place where `x` and `num1` disagree, so making it small means disagreeing as rarely as possible and, when a disagreement is unavoidable, putting it as low down as possible. The count of `1` bits in `x` is fixed by `num2`, and nothing else about `num2` matters. So spend the allowance from the top down on places where `num1` already carries a `1`: agreeing at a high place saves more than agreeing at any number of lower ones, since one high bit outweighs everything beneath it. If the allowance runs out before `num1`'s bits do, the leftover high bits of `num1` are disagreements that cannot be helped. If instead allowance is left over once every bit of `num1` is matched, the spare bits have to land on places where `num1` carries a `0`, and each one adds its own place to the answer. Putting them at the lowest free places keeps that addition as small as it can be.

Pythonentry point: minimize_xor

def minimize_xor(num1, num2):
    need = 0
    rest = num2
    while rest:
        need += rest & 1
        rest >>= 1
    x = 0
    for place in range(39, -1, -1):
        if need == 0:
            break
        if num1 >> place & 1:
            x |= 1 << place
            need -= 1
    for place in range(40):
        if need == 0:
            break
        if not (x >> place & 1):
            x |= 1 << place
            need -= 1
    return x

The obvious version

List every choice of bit places of the right size, within a width wide enough to hold any answer, build the number each choice describes and keep the one whose exclusive-or with `num1` is smallest. A place above both the width of `num1` and the allowance could only add to the answer, so nothing is missed. Costs the number of ways of choosing that many places.

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_minimize_xor(num1, num2):
    from itertools import combinations
    need = 0
    rest = num2
    while rest:
        need += rest & 1
        rest >>= 1
    width = num1.bit_length()
    if need > width:
        width = need
    width += 1
    best = None
    answer = None
    for spots in combinations(range(width), need):
        x = 0
        for place in spots:
            x |= 1 << place
        score = x ^ num1
        if best is None or score < best:
            best = score
            answer = x
    return answer

How this problem was checked

Reference solution executed against 15 test cases — 15 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