Closest XOR With a Bit Budget

Medium

You are given two positive integers base and pattern. Find the positive integer x that has as many set bits in binary as pattern does and makes x XOR base as small as possible. Return x. Such a number is always unique.

Example 1

base=10, pattern=7 → 11

10 = 1010₂, and 7 = 111₂ has three set bits. Take 1011₂ = 11: 11 XOR 10 = 1, which is as small as it gets.

Example 2

base=13, pattern=4 → 8

Only one set bit is allowed. Keep the top bit of 13 = 1101₂: x = 1000₂ = 8, and 8 XOR 13 = 5.

Example 3

base=6, pattern=9 → 6

Constraints

1 ≤ base, pattern ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Bit Manipulation

Similar problems

Steps Down to One Medium Best Binary Rows After Flips Medium Groups of Four at the Cinema Medium Bump One or Double All Medium Zero Out With Powers of Two Medium

Input

base=10, pattern=7

Expected

Run checks the first 3 tests in your browser. Submit checks all 63 tests on the server, hidden ones included.