C++ recursive method


  • 0
    J

    Just do it recursively, be careful with integer overflow.
    For a odd number we only have two choices -1 or +1, my idea is to reduce the problem size.

        int min(int a, int b){
            return a < b ? a:b;
        }
    
        int func(int n){
            if(n == 1) return 0;
            if(n  % 2 ){
                return min(func(n-1)+1 , func((n-1)/2 + 1) + 2);
            } else{
                return func(n/2) + 1;
            }
        }
    
        int integerReplacement(int n) {
            return func(n);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.