Minimum operations to convert number to 1

Question

Given a number N and number K, find minimum number of operations to convert N to 1. allowed operations:

subtract 1
divide by 2 (at most K times)

here is my code but it is not working correctly.

  private int getMinRounds(int N, int K, int memo[]) 
  { 
      if(N <= 1) return 0;
      if (memo[N] != -1) return memo[N];
      
      int rounds;
      if ((N%2) == 0 && K > 0) {
          rounds = 1 + Math.min(getMinRounds(N-1, K, memo), getMinRounds(N/2, K-1, memo));
      }else {
          rounds = 1 + getMinRounds(N-1, K, memo);
      }
      memo[N] = rounds; 
      return rounds; 
  }

  private int solution(int N, int K) 
  { 
      int memo[] = new int[N + 1];
      Arrays.fill(memo, -1);
      return getMinRounds(N, K, memo); 
  }

"*it is not working correctly*" **What** about it is not working correctly? Please be specific - don't leave potential answerers guessing. — esqew, Jul 29 '20 at 23:37
for example if N = 18 and K = 2. expected answer is 6 but it returns 5 — Andrew, Jul 29 '20 at 23:39
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) Or did you simply expect us to debug your code for you for free? — Andreas, Jul 29 '20 at 23:45
*Hint:* Try changing `memo` to a 2D array `int[N + 1][K + 1]`. The method has 2 independent arguments, so the result of calling with a particular `N` is not always the same, since the result also depends on `K`. — Andreas, Jul 29 '20 at 23:48
@Andreas thank you so much for the hint, I guess that exactly what I was missing. And sorry if my question wasn't clear or lacked information. — Andrew, Jul 29 '20 at 23:58
@rock It's not that the question is unclear or lacks information, it's that it lacks *work* on your part, i.e. the *attempt* at identifying the problem by **debugging** the code. See e.g. [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — Andreas, Jul 30 '20 at 00:01

Daniel · Accepted Answer · 2020-07-30T06:59:25.797

A greedy aproach should be enough to solve this problem. The bigger the number is, the best it is to divide it by 2 already, so you don't need to think "is it better to divide now or store the division for later?". The bigger the number you can divide is, the best for you it will be to divide it.

int solve (int n, int k){
    if(n == 1) return 0;
    if(k == 0) return n - 1;
    if(n % 2 == 0) return 1 + solve(n / 2, k - 1);
    return 1 + solve(n - 1, k);
}

Complexity: O(log(n))

OUTPUTS solve(n, k)

solve(1, 1) = 0
solve(2, 2) = 1
solve(3, 3) = 2
solve(4, 0) = 3
solve(5, 1) = 3
solve(6, 2) = 3
solve(7, 3) = 4
solve(8, 0) = 7
solve(9, 1) = 5
solve(10, 2) = 4

Minimum operations to convert number to 1

1 Answers1