Java solution. Accepted but not sure if the algorithm works on all situations.


  • 0
    Y

    '''
    public int integerReplacement(int n) {
    if (n <= 1) {
    return 0;
    } else if (n == Integer.MAX_VALUE) {
    return 32;
    }

        int count = 0;
        while (n > 1) {
            if ((n & 0x1) == 0) {
                n >>= 1;
            } else {
                if (Integer.lowestOneBit(n + 1) > Integer.lowestOneBit(n - 1)) {
                    int lowDiff = Integer.lowestOneBit(n + 1) / Integer.lowestOneBit(n - 1);
                    int highDiff = Integer.highestOneBit(n + 1) / Integer.highestOneBit(n - 1);
                    if (lowDiff > highDiff) {
                        n++;
                    } else {
                        n--;
                    }
                } else {
                    n--;
                }
            }
            count++;
        }
        return count;
    }
    

    '''

    The idea is to make a decision when it comes to odd case. We want more trailing 0 as much as possible. This is where comparison for lowestOntBit.

    For the highestOneBit comparison, if plus 1 or minus 1 get the same result, we compare the trailing 0s. If they are not same, higher one will need more steps. At this point we need to compare the steps it brings and the trailing 0 it brings.

    Please advice whether this algorithm is correct. Thanks!


Log in to reply
 

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