My recursive JAVA solution


  • 0
    public int integerReplacement(int n, int steps) {
    	  
    	  if(n <=1)
    		  return 0;
    	  if(n==1)
    		  return steps;
    	  if(n%2==0)
    			  return integerReplacement(n/2,steps+1);
    	  else return Math.min(integerReplacement(n+1, steps+1),integerReplacement(n-1,steps+1));
    	  
      }
    

  • 0
    L

    is that stackoverflow ?


  • 0

    OJ accepted it


  • 2
    L

    Your solution takes exponential time.
    I solved this problem using dynamic programming approach, which is an O(N) algorithm. But again, OJ told me "Memory Limit Exceeded". Any body got confused as I am.
    Here is my solution:

    	public int integerReplancementArr(int n) {
    		int[] dp = new int[n + 1];
    		dp[0] = Integer.MAX_VALUE;
    		dp[1] = 0;
    
    		for (int i = 2; i <= n; i++) {
    			if (i % 2 == 0)
    				dp[i] = dp[i / 2] + 1;
    			else {
    				dp[i] = Math.min(dp[i - 1], dp[(i + 1) / 2] + 1) + 1;
    			}
    		}
    
    		return dp[n];
    	}
    

  • 0

    @lzb700m There's a n = 2147483647 test case, that's why DP doesn't work here.


  • 0
    L

    @dettier I don't think that is the reason. My dp solution failed on n = 1000000 because of MLE.


  • 0

    @lzb700m Yes, that's exactly what i meant. That n could be large enough for DP solution to get MLE.


  • 0
    L

    @dettier How do you know what the limit of memory is? How do you konw that exponential running time is OK?


  • 0

    @lzb700m I don't think this solution is exponential. Worst case recurrence relation is T(n) = 2 * T(n / sqrt(2)) + c, which means that it is O(n^2) if I am not mistaken.
    Using 2147483647 * 4 bits is definitely over the memory limit on LeetCode for any problem.


  • 0

    @dettier, I'm curious how did you get that sqrt thing. I'd think that it's exponential in terms of number of 1's, which means linear in terms of n, but experiments don't confirm that. I get a few thousand calls at best, which indeed looks more like the number of digits squared.


  • 0

    @stachenov Well, for the worst case n halves every other step. So I guess n / sqrt(2) is a good way to model it.


  • 1

    @dettier, no, wait, that's not it. When you have two calls, n is guaranteed to halve on the next level, and there will be just one call on that level. So you might as well write 2T(n/2), only that makes it O(n) and that's not it either. I'm at a loss here. Perhaps it has something to do with the fact that in the worst case you only have two calls on every other level? Maybe it's something like O(sqrt(n)) because that's more like it, but I can't properly explain how it would be O(sqrt(n)).

    If it was O(n^2), it would TLE for INT_MAX. Even O(n) would take a while. And as I've said, I'm seeing at most few thousand calls even for tests like 0b1010101010....


  • 3

    @stachenov You are right!

    We can rewrite this solution like this to more easily reason about it:

    function integerReplacement(n, steps = 0) {
       if (n < 1) return 0;
       if (n === 1) return steps;
       if (n % 2 === 0) return integerReplacement(n / 2, steps + 1);
       else return Math.min(integerReplacement((n + 1) / 2, steps + 2),
                            integerReplacement((n - 1) / 2, steps + 2));
    }
    

    So number halves on every step now. And for the worst case only every other step makes 2 recursive calls.

    Do you think we can use T(n) = ((1 + 2) / 2) * T(n/2) + c as a model for this? This way it is O(n ^ log2(1.5)) = O(n ^ 0.585).


  • 0

    @dettier Yes, that's it! Not exactly O(sqrt(n)), but pretty close. And that recurrence makes perfect sense: we have 1.5 calls per level on average, and each call halves the problem size.


  • 0
    S

    I also implemented using same idea.

    public int integerReplacement(int n) {
        if (n <= 3) return n - 1;
        if (n % 2 == 0) return 1 + integerReplacement(n / 2);
        else return 1 + Math.min(integerReplacement(n - 1), 1 + integerReplacement(n / 2 + 1));
    }

  • 0

    @dettier
    That can be solved by using long instead of int. I agree that this is a slow solution, but OJ accepted it.

    public int integerReplacement(int n) {
        return countMin(n);
    }
    public int countMin(long n) {
        if(n == 1) return 0;
        if(n % 2 == 0) return countMin(n/2) + 1;
        return Math.min(countMin(n+1), countMin(n-1)) + 1;
    }

  • 0
    O

    @lzb700m I took the same approach, did you figure why DP does not work but recursion does here? Thx!


  • 0
    R

    @dettier You can add an additional base case for Max Int since its odd it will try to n+1 which would wrap around. So have it only consider n-1.


Log in to reply
 

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