Integer Replacement

Hard

Given a positive integer n, in one operation you may replace n by n / 2 if it is even, or by n + 1 or n - 1 if it is odd. Return the minimum number of operations needed for n to become 1.

Example 1

Input:  n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1.

Example 2

Input:  n = 7
Output: 4
Explanation: 7 -> 8 -> 4 -> 2 -> 1.

Example 3

Input:  n = 1
Output: 0

Constraints

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