1369. Integer Replacement — Min Steps Using Bits

Starting from a positive integer n, one operation halves it when it is even, or adds or subtracts one when it is odd. Return the minimum number of operations needed to reduce n to 1.

Input: A JSON object {"n": <positive integer>}.

Output: Return the minimum number of operations to reach 1.

Examples

Input: {"n":8}
Output: 3
Explanation: Halving three times reaches 1.

Input: {"n":7}
Output: 4
Explanation: Adding one to reach 8 then halving three times gives 4 operations.

Constraints

• 1 <= n <= 2^31 - 1

Asked by