A couple of Java solutions with explanations


  • 118

    I really think it should be tagged medium because there are many subtleties and good understanding of binary arithmetic is required.

    The first step towards solution is to realize that you're allowed to remove the LSB only if it's zero. And to reach the target as fast as possible, removing digits is the best way to go. Hence, even numbers are better than odd. This is quite obvious.

    What is not so obvious is what to do with odd numbers. One may think that you just need to remove as many 1's as possible to increase the evenness of the number. Wrong! Look at this example:

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

    And yet, this is not the best way because

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

    See? Both 111011 -> 111010 and 111011 -> 111100 remove the same number of 1's, but the second way is better.

    So, we just need to remove as many 1's as possible, doing +1 in case of a tie? Not quite. The infamous test with n=3 fails for that strategy because 11 -> 10 -> 1 is better than 11 -> 100 -> 10 -> 1. Fortunately, that's the only exception (or at least I can't think of any other, and there are none in the tests).

    So the logic is:

    1. If n is even, halve it.
    2. If n=3 or n-1 has less 1's than n+1, decrement n.
    3. Otherwise, increment n.

    Here is an example of such a solution in Java:

    public int integerReplacement(int n) {
        int c = 0;
        while (n != 1) {
            if ((n & 1) == 0) {
                n >>>= 1;
            } else if (n == 3 || Integer.bitCount(n + 1) > Integer.bitCount(n - 1)) {
                --n;
            } else {
                ++n;
            }
            ++c;
        }
        return c;
    }
    

    Of course, doing bitCount on every iteration is not the best way. It is enough to examine the last two digits to figure out whether incrementing or decrementing will give more 1's. Indeed, if a number ends with 01, then certainly decrementing is the way to go. Otherwise, if it ends with 11, then certainly incrementing is at least as good as decrementing (*011 -> *010 / *100) or even better (if there are three or more 1's). This leads to the following solution:

    public int integerReplacement(int n) {
        int c = 0;
        while (n != 1) {
            if ((n & 1) == 0) {
                n >>>= 1;
            } else if (n == 3 || ((n >>> 1) & 1) == 0) {
                --n;
            } else {
                ++n;
            }
            ++c;
        }
        return c;
    }
    

    An alternative approach to intuitive algorithm was very well put by @dettier in a discussion: you should create as many trailing zeroes as you can. This way you can avoid the tie-breaking trap (there can be no ties), but you'll still have to handle the n=3 exception separately.


  • 3
    H

    Excellent analysis. However, you should take care of the case where n is Integer.MAX_VALUE. We can't increment n but incrementing is the better way to get the trailing zeroes. One way is to check the corner case at the beginning of the loop.


  • 1

    @hayleyhu We can increment n, but it becomes negative. That's why I have while (n != 1) instead of while (n > 1). Cost me another 10 minutes of penalty time, that one.


  • 1
    X

    Splendid idea! But what's the difference between ">>>" and ">>"? Thanks.


  • 4

    @xinyao >>> is unsigned shift. It's needed because all Java types are signed (except char which is also considered an integer type for whatever crazy reason).


  • 0
    X

    Oh, I got. ">>>" means no operator right shift.


  • 3
    A

    Intuitive solution.
    Instead of "((n >>> 1) & 1) == 0" we could have just done "(n&3) == 1" for that if condition.


  • 0

    @aman13 Right. And we could (n % 4) == 1 or just analyze n % 4 or n & 3 to begin with. But it doesn't really matter.


  • 0
    L

    Nice solution.


  • 2
    F

    great solution! I tried DP but it uses too much space.


  • 0
    D

    @SergeyTachenov, great solution. I tried rewrite it to c++ code but it actually timeout. Do you know why this is the case?


  • 0

    @dukeforever Since you don't show your code, I can't possibly know what's wrong with it. I can only guess that it has something to do with signed/unsigned shifts. In Java I have to use >>>, in C/C++ you'd have to reassign n to an unsigned int first.


  • 0
    D

    @SergeyTachenov, I try assign n to unsigned int. It works. Thanks man!


  • 0
    I

    Thanks for providing a nice solution.


  • 0
    F

    Hi Sergey, thanks for your excellent explanation. I tried to implement your method but failed in the case of “2147483647”, the only difference between your answer and mine is in the right shift operator. You use “>>>” to do the right shift while I use >> to shift 1 bit, is “>>>” more efficient than “>>” in Java?


  • 3

    @flyinghenanese It has nothing to do with efficiency. See the discussion above. >>> is the unsigned shift, >> is the signed shift. When you increment MAX_INT it becomes negative, so all your subsequent shifts don't work properly. For the same reason the loop uses n != 0 instead of n > 0.


  • 0
    F

    @SergeyTachenov Thank you so much.


  • 0
    F

    Nice answer and briliant explanation! But Maybe there is a mistake in this sentence."Otherwise, if it ends with 11, then certainly incrementing is at least as good as incrementing (*011 -> *010 / *100) or even better (if there are three or more 1's)". Should the second incrementing be decrementing?


  • 0
    F

  • 0

    @fk961859482 50 upvotes, and you're the first one to notice! Thanks, fixed.


Log in to reply
 

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