C++ solution


  • 0
    Y
    //Reference : 
    class Solution {
    public:
        // The keypoint is how to make sure that we can halve n as many times as possible.
        // Put it in another way, we want to divede n by 2 as many times as possible.
        // Which means, if there is any chance that we can convert n to be multiple of 4,
        // we should do that without hesitation.
        // The only exception is number 3, since the only reason we convert n to be muptile of 4 
        // is that we can "divide n by 4" in our recursion path. 
        int integerReplacement(int n) {
            // we know the input is always positive
            if (n==1) return 0;
            if (n == INT_MAX)
                return 32;
            if (n==3) return 2;
            if (n%2==0) {
                return 1+integerReplacement(n/2);
            } else {
                if ( (n+1)%4==0) {
                    return 1 + integerReplacement(n+1);
                } else {
                    return 1 + integerReplacement(n-1);
                }
            }
        }
    };
    
    class Solution {
    public:
        // The keypoint is how to make sure that we can halve n as many times as possible.
        // Put it in another way, we want to divede n by 2 as many times as possible.
        // Which means, if there is any chance that we can convert n to be multiple of 4,
        // we should do that without hesitation.
        // The only exception is number 3, since the only reason we convert n to be muptile of 4 
        // is that we can "divide n by 4" in our recursion path. 
        int integerReplacement(int n) {
            if (n==INT_MAX) return 32;
            // we know the input is always positive
            int count(0);
            while(n!=1) {
                if (n%2==0) {
                    n /= 2;
                } else {
                    if ( (n+1)%4==0 && n>4) {
                        ++n;
                    } else {
                        --n;
                    }
                }
                
                ++ count; // increase replacement count
            }
            return count;
        }
    };
    

Log in to reply
 

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