Is this greedy solution correct?


  • 0
    T

    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;
        }
    };
    

  • 0

    @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.


  • 0

    @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.


  • 0

    @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.


  • 0

    @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).


  • 0

    @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".


  • 0

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


Log in to reply
 

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