Down to Zero II

To explore all solution tree and find globally optimal solution, we must choose the best result both from all possible divisor pairs and from solution(n-1)

My weird translation to Java (ideone) uses bottom-up dynamic programming to make execution faster.

We calculate solutions for values i from 1 to n, they are written into table[i].

At first we set result into 1 + best result for previous value (table[i-1]).

Then we factor N into all pairs of divisors and check whether using already calculated result for larger divisor table[d] gives better result.

Finally we write result into the table.

Note that we can calculate table once and use it for all Q queries.

class Ideone
{
    public static int makezeroDP(int n){
       int[] table = new int[n+1];
       table[1] = 1; table[2] = 2; table[3] = 3;
       int res;
       for (int i = 4; i <= n; i++) {
          res = 1 + table[i-1];
          int a = 2;
          while (a * a <= i) {
             if (i % a == 0)
                res = Math.min(res, 1 + table[i / a]);
             a += 1;
          }
          table[i] = res;
       }
       return table[n];
    }
     
    public static void main (String[] args) throws java.lang.Exception
    { 
        int n = 145;//999999;
        System.out.println(makezeroDP(n));
    }
}

Old part

Simple implementation (sorry, in Python) gives answer 7 for 7176

def makezero(n):
    if n <= 3:
        return n
    result = 1 + makezero(n - 1)
    t = 2
    while t * t <= n:
        if n % t == 0:
            result = min(result, 1 + makezero(n // t))
        t += 1
    return result

In Python it's needed to set recursion limit or change algorithm. Now use memoization, as I wrote in comments).

t = [-i for i in range(1000001)]
def makezeroMemo(n):
    if t[n] > 0:
        return t[n]
    if t[n-1] < 0:
        res = 1 + makezeroMemo(n-1)
    else:
        res = 1 + t[n-1]
    a = 2
    while a * a <= n:
        if n % a == 0:
            res = min(res, 1 + makezeroMemo(n // a))
        a += 1
    t[n] = res
    return res

Bottom-up table dynamic programming. No recursion.

def makezeroDP(n):
    table = [0,1,2,3] + [0]*(n-3)
    for i in range(4, n+1):
        res = 1 + table[i-1]
        a = 2
        while a * a <= i:
            if i % a == 0:
                res = min(res, 1 + table[i // a])
            a += 1
        table[i] = res
    return table[n]

We can construct the directed acyclic graph quickly with a sieve and then compute shortest paths. No trial division needed.

Time and space usage is Θ(N log N).

n_max = 1000000
successors = [[n - 1] for n in range(n_max + 1)]
for a in range(2, n_max + 1):
    for b in range(a, n_max // a + 1):
        successors[a * b].append(b)
table = [0]
for n in range(1, n_max + 1):
    table.append(min(table[s] for s in successors[n]) + 1)
print(table[7176])

Results:

7

EDIT:

The algorithm uses Greedy approach and doesn't return optimal results, it just simplifies OP's approach. For 7176 given as example, below algorithm returns 10, I can see a shorter chain of 7176 -> 104 -> 52 -> 13 -> 12 -> 4 -> 2 -> 1 -> 0 with 8 steps, and expected answer is 7.

Let's review your problem in simple terms.

If we take 2 integers a and b where N=a*b (a ,b cannot be equal to 1), then we can change N=max(a,b) and

Determine the minimum number of moves required to reduce the value of to .

You're looking for 2 factors of N, a and b and, if you want the minimum number of moves, this means that your maximum at each step should be minimum. We know for a fact that this minimum is reached when factors are closest to N. Let me give you an example:

36 = 1 * 36 = 2 * 18 = 3 * 12 = 4 * 9 = 6 * 6

We know that sqrt(36) = 6 and you can see that the minimum of 2 factors you can get at this step is max(6, 6) = 6. Sure, 36 is 6 squared, let me take a number without special properties, 96, with its square root rounded down to nearest integer 9.

96 = 2 * 48 = 3 * 32 = 4 * 24 = 6 * 16 = 8 * 12

You can see that your minimum value for max(a, b) is max(8, 12) = 12, which is, again, attained when factors are closest to square root.

Now let's look at the code:

for (int i=1;i<=n;i++){
  for (int j=1;j<=n;j++){
    if (i*j==n){

You can do this in one loop, knowing that n / i returns an integer, therefore you need to check if i * (n / i) == n. With the previous observation, we need to start at the square root, and go down, until we get to 1. If we got i and n / i as factors, we know that this pair is also the minimum you can get at this step. If no factors are found and you reach 1, which obviously is a factor of n, you have a prime number and you need to use the second instruction:

Decrease the value of N by 1 .

Note that if you go from sqrt(n) down to 1, looking for factors, if you find one, max(i, n / i) will be n / i.

Additionally, if n = 1, you take 1 step. If n = 2, you take 2 steps (2 -> 1). If n = 3, you take 3 steps (3 -> 2 -> 1). Therefore if n is 1, 2 or 3, you take n steps to go to 0. OK, less talking, more coding:

static int downToZero(int n) {
    if (n == 1 || n == 2 || n == 3) return n;
    int sqrt = (int) Math.sqrt(n);
    for (int i = sqrt; i > 1; i--) {
        if (n / i * i == n) {
            return 1 + downToZero(n / i);
        }
    }
    return 1 + downToZero(n - 1);
}

Notice that I'm stopping when i equals 2, I know that if I reach 1, it's a prime number and I need to go a step forward and look at n - 1.

However, I have tried to see the steps your algorithm and mine takes, so I've added a print statement each time n changes, and we both have the same succession: 7176, 92, 23, 22, 11, 10, 5, 4, 2, 1, which returns 10. Isn't that correct?

So, I found a solution which is working for all the test cases -

static final int LIMIT = 1_000_000; 
static int[] solutions = buildSolutions();

public static int downToZero(int n) {
    // Write your code here
    return solutions[n];
}
static int[] buildSolutions() {
    int[] solutions = new int[LIMIT + 1];
    for (int i = 1; i < solutions.length; i++) {
        solutions[i] = solutions[i - 1] + 1;

        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                solutions[i] = Math.min(solutions[i], solutions[i / j] + 1);
            }
        }
    }
    return solutions;
}
}