4ms recursive Java solution explained


  • 1
    H
    public class Solution {
        public int integerReplacement(int n) {
            if (n == 1) {
                return 0;
            } else if (n == 3) {
                return 2;
            } else if (n == 2147483647) {
                return 2 + integerReplacement((n >> 1) + 1);
            }
            if (n % 2 == 0) {
                return integerReplacement(n >> 1) + 1;
            }
            else {
                return numTrailingOnes(n) > 1 ? integerReplacement(n + 1) + 1 : integerReplacement(n - 1) + 1;
            }
        }
    
        private int numTrailingOnes(int num) {
            int shift = 0;
            while (((num >> shift) & 1) == 1) {
                shift++;
            }
            return shift;
        }
    }
    

  • 0
    H

    A straightforward thought about this problem is that we can write a divide-and-conquer recursive solution:

    1. if n is even, the answer is (integerReplacement(n / 2) + 1)
    2. if n is odd, the answer is MIN{integerReplacement(n + 1) + 1, integerReplacement(n - 1) + 1}

    However, this solution exceeds stack limit because the number of calls to the method is huge when n is huge.

    A second thought is dynamic programming: using an array A to store the result where A[i] = integerReplacement(i), and update A[0], A[1], ... A[n] one after another. In this way we can get the result in O(n) time. However, consider when n = 2147483647, this array could take ~16GB memory so that's not allowed for sure.

    So we return to the recursion idea, the problem is that when we use MIN{integerReplacement(n + 1) + 1, integerReplacement(n - 1) + 1}, the recursion tree begin to have two branches, and each branch could have sub-branches and so on. We can prune the tree by letting each node only have one child, in other word, we make a concrete decision whether to go to (n + 1) or (n - 1) when n is odd rather than using the comparison between two recursions.

    It is hard to think whether n+1 is better or vice versa. But if we consider the binary form, we can tell that the only thing that matters is the number of trailing 1s. If the number of trailing 1s is greater than one then we should use (n + 1). Use (n - 1) only when there is only one trailing 1, for example:

    1. n = xxxxx0111, three trailing 1s so we use n+1 which is xxxxx1000, because this makes more trailing 0s, so that we can use >> to get n/2.
    2. n = xxxxx0001, one trailing 1 so we use n-1 which is xxxxx0000.

    Just keep in mind two important things:

    1. the trailing 1s all become zero when you add one to the number
    2. when a number has k trailing zeroes, it could be divided by 2^k

    n = 3 and n = 2147483647 are two special cases we need to take care of in the beginning.


  • 0
    W

    Thank you, a nice solution.

    But I don't understand why do you handle n==Integer.MAX_VALUE like this.

    Integer.MAX_VALUE is an odd number, shouldn't we -1 and >>1 ?

    I don't understand why you >>1 and +1

    Thank you.


  • 0
    H

    @wilbur_zzz For 2147483647 "-1 and >>1" is not the optimal move, normally we want to +1 to get 2147483648 (100...0, thirty-one 0s) and >> till it becomes 1, however the number is special in that it would exceed the bit limit of Integer and become -2147483648.

    So my solution is just using our mind to do the first two step and let the code continue from there and get the rest number of moves:

    2147483647(111....1, thirty-one 1s)
    |
    2147483648 (1000...0, one 1 and thirty-one 0s)
    |
    1073741824 (100...0, one 1 and thirty 0s), took 2 step to arrive at this number, now Integer can handle it, let the code continue from here
    |
    ... do >> thirty times
    |
    1
    Done! altogether 32 steps.

    Your idea is to -1 and >>, it takes 2 steps to get 1073741823 (111...1, thirty 1s). The best way to deal with it is to add one to get 1073741824, so you took 3 steps to get this number. Altogether 33 steps.

    Note that for numbers whose number of trailing ones is greater than 1, adding one is always better, except for one case: n = 3.


  • 0
    W

    @he17 I got it. Thank you so much. My mistake was, 2147483647 is the limit of integer in java, not in real world. I thought we should avoid the existence of 2147483648 not only in code, but also in mind.

    Thank you for your reply.


Log in to reply
 

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