Switch Off Bits to Match

Easy

You are given two positive integers start and target. In one move you may pick any bit of start that is 1 and turn it into 0. Turning a 0 into a 1 is not allowed. Return the smallest number of moves after which start equals target, or -1 if that cannot be done.

Example 1

start=29, target=9 → 2

29 = 11101₂ and 9 = 01001₂. Switching off two 1s (bits 4 and 2) turns it into 9.

Example 2

start=6, target=5 → -1

6 = 110₂ and 5 = 101₂. The lowest bit is 1 in 5 but 0 in 6, and bits can never be switched on, so the answer is -1.

Example 3

start=40, target=40 → 0

Constraints

1 ≤ start, target ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation

Similar problems

Sum of Binary Strings Easy The Unpaired Value Easy Flip the Bit Order Easy Count the Set Bits Easy Size of a Packed Tree Easy

Input

start=29, target=9

Expected

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