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

• ``````    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;
count++;
} else { // nothing happens here when debt == 0
count += debt;
debt = 0;
}
}
n = n >>> 1;
count++;
}
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.

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