Shifted Powers of Two

Medium

You are given integers start and shift. In one move you pick an integer i from 0 to 60 and subtract 2^i + shift from start. Return the minimum number of moves after which start becomes exactly zero, or -1 if that is impossible.

Example 1

start=7, shift=1 → 2

With one move the power of two would have to be 7 − 1 = 6, which is not a power of two. With two moves two powers of two must add up to 7 − 2 = 5 = 4 + 1: subtract 4 + 1 = 5 and then 1 + 1 = 2. The answer is 2.

Example 2

start=4, shift=5 → -1

Even the smallest amount, 2⁰ + 5 = 6, exceeds 4, and the number only goes down from there, so it can never hit zero.

Example 3

start=12, shift=-4 → 1

Constraints

1 ≤ start ≤ 10⁹
-10⁹ ≤ shift ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Brainteaser Enumeration

Similar problems

Take From Any Pile Medium Picks With the Full OR Medium Outshoot the Rival Medium Columns That Cover Rows Medium Longest Stretch with the Top AND Medium

Input

start=7, shift=1

Expected

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