# Is this greedy solution correct?

• This solution is accepted by the online judge system. But I cannot figure out why.

``````/**
* @param {number} n
* @return {number}
*/
var integerReplacement = function(n) {
if (n < 4) return [0, 0, 1, 2][n];
switch (n % 4) {
case 0: case 2: return integerReplacement(n / 2) + 1;
case 1: return integerReplacement((n - 1) / 4) + 3;
case 3: return integerReplacement((n + 1) / 4) + 3;
}
};
``````

• @ts Yes, I am sure this solution is correct.
The idea is that you better remove as many binary 1's as you can for odd numbers. So if n ends with "11" (binary) you add 1 (except for n == 3), and if it ends with "01" you do -1.

• @dettier not exactly. This solution is correct, but you can't just remove as many 1's as you can. Because with a number ending in 011, both +1 and -1 give you equal number of 1's (100 vs 010), but +1 is better because 011 -> 100 -> 10 -> 1 vs 011 -> 010 -> 01 -> 00 -> 0. Because of this, I'm 72nd today, while I could be in the first 20.

• @stachenov Your example is not correct because your first sequence goes to 1 and the second one to 0, the correct example would be

``````X011 -> X100 -> X10 -> X1 -> X0 -> X
X011 -> X010 -> X01 -> X00 -> X0 -> X
``````

So for 011 there is no difference to do +1 or -1.
The only exception is n == 3 when there is no X part in the number.

• @dettier, it's not exactly incorrect, rather it's incomplete. OK, there is a full example how this logic fails:

``````111011 -> 111010 -> 11101 -> 11100 -> 1110 -> 111 -> 1000 -> 100 -> 10 -> 1
``````

vs

``````111011 -> 111100 -> 11110 -> 1111 -> 10000 -> 1000 -> 100 -> 10 -> 1
``````

So, ties should always be broken by incrementing (except for 3).

• @stachenov So I guess the best way to express the idea is the following: for odd numbers you should create as many trailing zeroes as you can (except for n == 3). So it is better to do +1 for "11" and -1 for "01".

• @dettier, yes, that's an excellent way to put it!

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