Think of '1' bits as debts! No edge case handling. With explaination

  • 1
        public int integerReplacement(int n) {
            int count = 0;
            int debt = 0;
            while(n > 1) {
                if((n & 1) == 1) debt++;
                else {
                    if(debt > 1) {
                        debt = 1;
                    } else { // nothing happens here when debt == 0
                        count += debt;
                        debt = 0;
                n = n >>> 1;
            return count + Math.min(debt, 2);

    Only look at the last bit.

    If it is 0 simply shift right.

    If it is 1 we still shift right. However, it is a debt and we need to pay for it later, there are 2 ways to pay it (-1 and +1).

    10000001 debt is created after the first shift. it will be payed in the next iteration. the cost of paying this debt is 1.

    10001111 we can pay all debts one by one (minus 1 operation), that will cost 4. Or we can transform the debt into 10010000 (plus 1 operation), which cost 1. it clears the old debt, but creates a new debt.

    More complex example:

    100111101111. There are 2 blocks of debts. Starting from the right one. We take 1 turn to convert the right debt, and it becomes, 100111110000. The two block of debts are merged into one. Then it got further converted into 101000000000.

    When last digit is 0, we review our debts. When the cost of paying the debt is 1 we pay for it and clear the debt. Otherwise we convert all debts into one debt to be payed in the future.

Log in to reply

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