0 ms C++ recursion solution with Explanation


  • 8

    All you need is determine replace n with n + 1 or n - 1, when n is odd. since,

    • if n is even, you get no choice, just replace it with n / 2.
    • if n is odd, you can either add 1 or reduce 1.

    If n + 1 % 4 == 0, replace n with n + 1 will short the path. Otherwise, replace n with n - 1 is always the right direction.

    Examle:

    Input:
    31
    
    - 1. Replace 31 with 32:
    31 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1
    
    - 2. Replace 31 with 30:
    31 -> 30 -> 15 -> 16 -> 8 -> 4 -> 2 -> 1
    
    Output:
    6
    

    Code:

    class Solution 
    {
        // date: 2016-09-11     location: Vista Del Lago III Apartments
        int res = 0;
    public:
        int integerReplacement(int n) 
        {
            if (n == 1)
                return res;
            if (n == 3)
            {
                res += 2;
                return res;
            }
            if (n == INT_MAX)
                return 32;
            if (n & 1)     // odd
            {
                res ++;
                if ((n + 1) % 4 == 0)
                    integerReplacement(n + 1);
                else
                    integerReplacement(n - 1);
            }
            else     // even
            {
                res ++;
                integerReplacement(n / 2);
            }
            return res;
        }
    };
    

    make it shorter:

    class Solution 
    {
        // date: 2016-09-11     location: Vista Del Lago III Apartments
        int res = 0;
    public:
        int integerReplacement(int n) 
        {
            if (n == 1)
                return res;
            if (n == 3)
            {
                res += 2;
                return res;
            }
            if (n == INT_MAX)
                return 32;
            
            res ++;
            if (n & 1)
                if ((n + 1) % 4 == 0)
                    integerReplacement(n + 1);
                else
                    integerReplacement(n - 1);
            else
                integerReplacement(n / 2);
                
            return res;
        }
    };
    

  • 2

    @Mad_air Thanks for sharing your brilliant code! I can not image how you came up with this great idea. The only question I want to know is that how to prove that conclusion. Can you give me some ideas?


  • 0
    K

    @Mad_air it's great ! But could you please prove your method or show me how you came about this ideas? Thank you~


  • 3
    G

    @yanchao_hust

    1.when the input number is even, just recursively divide by 2;

    1. when the input number is odd, assume current result is X, we need to consider two cases:
      2.1 plus 1: assume the input number is 2n+1, the number become 2n+2 after we plus one. so current number is definitely a even number, the current result is X+1,the next replacement also could be 2 cases:
      2.1.1: 2n+2/2 is odd number: this should not be considered because replace a odd numer to a even number we need one more replacement to plus 1or minus 1. the current result is:X+2
      2.2.2: 2n+2/2 is even number: this is we should focus because current number is a even number, we don't need do anything but recursively divided by 2. the current result is X+1; X+1<X+2 meet the requirement.

      2.2minus 1: same as plus 1...


  • 6
    K

    @Garlicala Maybe we can consider this problem in another way. We consider n is a binary number.
    When n is even, we just recursively divide by 2, it's the same as you.
    When n is odd, we consider the tail number of the binary number n, for example, when the tail is 01 we should minus 1, and when the tail is 11 or 111, we should plus 1, to make it can be divided to 1 faster.


  • 0

    @Garlicala Thanks for your explanation. I can understand the instinct. But I need proof to prove the conclusion.


  • 0
    S

    said in 0 ms C++ recursion solution with Explanation:

    if (n == INT_MAX)
            return 32;
    

    why is this check needed?


  • 1

    @sean46

    Thank you for posting. This check can avoid overflow, since in the following if statement, the program is gonna use (n + 1).


  • 0
    S

    @Mad_air

    Understood, thanks.


  • 0
    R

    @Mad_air You can convert n to a long type to avoid the check.


  • 1
    G

    No need to convert the type of n and no need to use a private attribute to save the result.

    class Solution {
    public:
        int integerReplacement(int n) {
            if (n == 1) return 0;
            if (n % 2 == 0) return 1 + integerReplacement(n / 2);
            if (n == 3) return 2;
            return n % 4 == 3 ? 2 + integerReplacement(n / 2 + 1) : 2 + integerReplacement(n / 2);
        }
    };
    

  • 1

    I think this is better

    class Solution {
    public:
        int integerReplacement(int n) {
            if (n == INT_MAX) return 32;
            if (n == 1) return 0;
            if (n == 3) return 2;
            if (n & 1) return n % 4 == 3 ? 1 + integerReplacement(n + 1) : 1 + integerReplacement(n - 1);
            return 1 + integerReplacement(n / 2);
        }
    };
    

  • 0
    L

    @yanchao_hust we first prove that if k = 2m, integerReplacement(k) <= integerReplacement(k+1) && integerReplacement(k) <= integerReplacement(k-1).
    because integerReplacement(k) = 1+integerReplacement(m);
    integerReplacement(k+1) = min(2+integerReplacement(m), 2+integerReplacement(m+1));
    if m = 2s+1, we can have a transfer of m->m+1, so integerReplacement(k) = 1+integerReplacement(m) <= 2+integerReplacement(m+1), and integerReplacement(k) = 1+integerReplacement(m) < 2 + integerReplacement(m), so integerReplacement(k) <= integerReplacement(k+1);
    if m = 2s, we can use mathematical induction to prove it easily;
    so if k = 2m, integerReplacement(k) <= integerReplacement(k+1).
    and just the same as if k = 2m, integerReplacement(k) <= integerReplacement(k-1).
    Now we prove that integerReplacement(4k) <= integerReplacement(4k+2) and integerReplacement(4k) <= integerReplacement(4k-2)
    integerReplacement(4k) = 1+integerReplacement(2k); integerReplacement(4k+2) = 1+integerReplacement(2k+1);
    use the provement above, we can see integerReplacement(2k) <= integerReplacement(2k+1), so integerReplacement(4k) <= integerReplacement(4k+2);
    the same as integerReplacement(4k) <= integerReplacement(4k-2).


  • 0
    Y

    great improvement for odd number!!!.

    brute force recursive version.

        private static Map<Integer, Integer> cnt = new HashMap<>();
        public int integerReplacement(int n) {
            if (cnt.containsKey(n)) return cnt.get(n);
            
            if (n <= 1) { cnt.put(n, 0); return 0; }
    
            int counts = 0;
            if (n % 2 == 0) counts = 1 + integerReplacement(n >> 1);
            else            counts = 1 + Math.min(1 + integerReplacement((int)(((long)n + 1) >> 1)), integerReplacement(n - 1));
            
            cnt.put(n, counts);
            return counts;        
    
        }
    

  • 0
    Y
    This post is deleted!

  • 0
    M

    Inspired by your idea.

    We don't need to check INT_MAX. The only thing we need to check is 3, which means n starts with two consecutive ones.

    There are three cases:

    1. If n is even, then divide n by 2.
    2. If n has the tail like 11 or 111 or 1111..., then do n++.
    3. If n has the tail like 01, then do n--.

    Why n = 3 is a special case?
    Because the shortest path is
    3 (000...00011) -> 2 (000...00010) -> 1 (000...00001)
    not
    3 (000...00011) -> 4 (000...00100) -> 2 (000...00010) -> 1 (000...00001)
    And for other numbers start with two consecutive 1 (such as 0x11001 or 0x11000), the leading 11 is of this special case.

    class Solution {
    public:
        int integerReplacement(int n) {
            int ans = 0;
            while(n != 1){
                if(n == 3)              // special case: n start with two consecutive 1 
                    return ans+2;
                else if((n & 0x1) == 0) // n is odd
                    n = (n >> 1) & 0x7FFFFFFF;
                else if((n+1) % 4 == 0) // n has tail like 0x11, 0x111, ...
                    n++;
                else                    // n has tail like 0x01
                    n--;
                ans++;
            }
            return ans;
        }
    };
    

Log in to reply
 

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