Find the minimum number of steps to decrease N to zero

Question

I'm facing some difficulties in the last few days while trying to finish the following task, I hope you guys can assist :

I'm given a single number N, and I'm allowed to perform any of the two operations on N in each move :

One - If we take 2 integers where N = x * y , then we can change the value of N to the maximum between x and y.

Two - Decrease the value of N by 1.

I want to find the minimum number of steps to reduce N to zero. This is what I have so far, I'm not sure what is the best way to implement the function to find the divisor (someFindDevisorFunction), and if this 'f' function would actually produce the required output.

  int f(int n)
{
  int div,firstWay,secondWay;
  if(n == 0)
    return 0;

  div = SomefindDivisorFunction(n);
  firstWay = 1 + f(n-1);
  if(div != 1)
  {
    secondWay = 1 + f(div);
    if (firstWay < secondWay)
        return firstWay;
    return secondWay;
  }

  return firstWay;
}

For example, if I enter the number 150 , the output would be : 75 - 25 - 5 - 4 - 2 - 1 - 0

Answer 1

I see this a recursive or iterative problem.

OP's approach hints at recursive.

---

A recursive solution follows:

At each step, code counts the steps of the various alternatives:

steps(n) = min(
  steps(factor1_of_n) + 1,
  steps(factor2_of_n) + 1,
  steps(factor3_of_n) + 1,
  ...
  steps(n-1) + 1)

The coded solution below is inefficient, but it does explore all possibilities and gets to the answer.

int solve_helper(int n, bool print) {
  int best_quot = 0;
  int best_quot_score = INT_MAX;
  int quot;
  for (int p = 2; p <= (quot = n / p); p++) {
    int rem = n % p;
    if (rem == 0 && quot > 1) {
      int score = solve_helper(quot, false) + 1;
      if (score < best_quot_score) {
        best_quot_score = score;
        best_quot = quot;
      }
    }
  }

  int dec_score = n > 0 ? solve_helper(n - 1, false) + 1 : 0;

  if (best_quot_score < dec_score) {
    if (print) {
      printf("/ %d ", best_quot);
      solve_helper(best_quot, true);
    }
    return best_quot_score;
  }
  if (print && n > 0) {
    printf("- %d ", n - 1);
    solve_helper(n - 1, true);
  }
  return dec_score;
}

int main() {
  int n = 75;
  printf("%d ", n);
  solve(n, true);
  printf("\n");
}

Output

75 / 25 / 5 - 4 / 2 - 1 - 0 

---

Iterative

TBD