Nearest Code With Fixed Ones

MediumBit Manipulation

Problem

A badge printer can only encode IDs with exactly onesCount set bits. A visitor asked for the ID target, which may not qualify, so the printer picks the qualifying ID x that is closest in the XOR sense: x XOR target is as small as possible.

Return that x. It is always unique.

Example 1

Input:
target = 25, onesCount = 2
Output:
24

25 = 11001. Keeping its two highest set bits gives 11000 = 24, and 24 XOR 25 = 1.

Example 2

Input:
target = 1, onesCount = 2
Output:
3

target has one set bit; the extra bit goes to the lowest free position: 11.

Example 3

Input:
target = 3, onesCount = 2
Output:
3

Constraints

  • 0 ≤ target < 2^30
  • 1 ≤ onesCount ≤ 30

Hint

Show the first hint

x XOR target is small when x agrees with target on the high bits. Which bits should x try to copy first?

Walkthrough

How to approach it

01Clarify before coding

  • Is x unique? Yes, the greedy choice below is forced at every bit, so there is exactly one best x.
  • Can x exceed 2^30? No: onesCount ≤ 30 and positions 0..29 always have room, so x stays below 2^30.
  • Can target be 0? Yes; then x is the onesCount lowest bits.

02Brute force

Try every x below 2^30 with the right popcount and keep the one with the smallest XOR.

Cost: O(2^30) candidates: hopeless.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.