Integer Replacement
Given a positive integer n, you can apply one of the following operations:
- If
nis even, replacenwithn / 2. - If
nis odd, replacenwith eithern + 1orn - 1.
Return the minimum number of operations needed for n to become 1.
Example 1
Input
n = 8Output
3Starting from 8, the sequence 8 -> 4 -> 2 -> 1 takes 3 operations.
Example 2
Input
n = 7Output
4Starting from 7, either 7 -> 8 -> 4 -> 2 -> 1 or 7 -> 6 -> 3 -> 2 -> 1 takes 4 operations.
Constraints
- 1 <= n <= 2^31 - 1