Given a positive integer n,&nbsp;you can apply one of the following&nbsp;operations:


	If n is even, replace n with n / 2.
	If n is odd, replace n with either n + 1 or n - 1.


Return the minimum number of operations needed for n to become 1.

&nbsp;
Example 1:

Input: n = 8
Output: 3
Explanation: 8 -&gt; 4 -&gt; 2 -&gt; 1


Example 2:

Input: n = 7
Output: 4
Explanation: 7 -&gt; 8 -&gt; 4 -&gt; 2 -&gt; 1
or 7 -&gt; 6 -&gt; 3 -&gt; 2 -&gt; 1


Example 3:

Input: n = 4
Output: 2


&nbsp;
Constraints:


	1 &lt;= n &lt;= 231 - 1


class Solution:
    def integerReplacement(self, n: int) -> int:
        dp = {}
        def dfs(num):
            if num == 1:
                return 0

            if num in dp:
                return dp[num]

            # if num is even, we have only one option -> n / 2
            even = odd = 0
            if num % 2 == 0:
                even = 1 + dfs(num // 2)
            else:
                # if num is odd, we have two option, either we increment the num or decrement the num
                odd1 = 1 + dfs(num - 1)
                odd2 = 1 + dfs(num + 1)
                # take the min of both operation
                odd = min(odd1, odd2)

            dp[num] = even + odd
            return dp[num]

        return dfs(n)
class Solution {
    public int integerReplacement(int n) {
        return (int)calc(n,0);
    }
    public long calc(long n,int i){
        if(n==1) 
            return i;
        if(n<1) 
            return 0;
        
        long a=Long.MAX_VALUE,b=Long.MAX_VALUE,c=Long.MAX_VALUE;
        
        if(n%2==0) 
            a=calc(n/2,i+1);
        else{
            b=calc(n-1,i+1);
            c=calc(n+1,i+1);
        }
        long d=Math.min(a,Math.min(b,c));
        return d;
    }
}
class Solution {
public:
    int integerReplacement(int n) {

        return helper(n);
    }

    int helper(long n)
    {
        if(n == 1)
            return 0;

        if(n % 2)
            return 1 + min(helper(n - 1), helper(n + 1));

        return 1 + helper(n / 2);
    }
};
var integerReplacement = function(n) {
    let count=0;
    while(n>1){
       if(n%2===0){n/=2;}
       else{
         if(n!==3 && (n+1)%4===0){n++;}
         else{n--;}
       } 
      count++;  
    }
    return count;  
};        
Integer Replacement