[java/4ms] iterative, greedy, explained in detail.


  • 1

    if n > 1, you need to divide by 2 to decade faster. No matter you add or minus 1, your target is to make it even and then divide by 2.

    Here, if n is even, then divide by 2.

    Otherwise, if n is odd, then it depends on m = n / 2. if m is odd, we will add or minus 1 in next step. If m is even, then we will save one step instead.

    However n = 3 is the outlier because the difference of 1 matters, see below.

    For instance: n = 39
    m = n / 2 = 19, we can
    39 -> 40 -> 20
    39 -> 38 -> 19 -> 20 or 18 in the next step.

    As you can see, if we use divide by 2 to mark a step, then for every step, the mid result of choosing + or - 1 will have a difference of 1 (e.g. 20 and 19). We can treat them as if they are of no difference. However 19 will require an extra step in next step.

    public int integerReplacement(int n) {
            int cnt = 0;
            while (n > 1) {
                cnt++;
                if ((n & 1) != 0) {
                    cnt++;
                    n >>= 1;
                    if (n != 1 && (n & 1) != 0) n++;
                } else {
                    n >>= 1;
                }
            }
            
            return cnt;
        }
    

Log in to reply
 

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