C++ iterative solution


  • 0
    H

    To minimize the number of replacements, we should make n decrease to 1 as soon as possible. In other word, try to make it as even number as many times as possible. Because we can only do either n+1 or n-1, the only thing we can do is to make the number divisible by 4. Then we can make sure it will fall into even number at least twice in following replacement. 3 is an exception because it will become to 1 right after minus 1 and divide 2. INT_MAX is another corner case.

    class Solution {
    public:
        int integerReplacement(int n) {
            int res = 0;
            while (n > 1) {
                if (n == INT_MAX) {n >>= 1; n++; res++;}
                else if (n&1 && (n == 3 || (n+1)%4)) n--;
                else if (n&1) n++;
                else n >>= 1;
                res++;
            }
            return res;
        }
    };
    

Log in to reply
 

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