Show problems as
Classic problem #2429MediumGreedyBit Manipulation

Minimize XOR

Real-world version: Matching the Notch Count as Closely as You Can
Tracked in this browser only
Read Minimize XOR on LeetCode(opens in a new tab)

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

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

Python
def minimize_xor(num1: int, num2: int) -> int:
Java
public int minimizeXor(int num1, int num2)

More on the same topics