Down to Zero II

This is the question:

You are given Q queries. Each query consists of a single number N . You can perform any of the operations on in each move:

1. 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)

2. Decrease the value of N by 1 .

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

Input Format

The first line contains the integer Q.
The next Q lines each contain an integer,N .

Output Format

Output Q lines. Each line containing the minimum number of moves required > to reduce the value of N to 0.

I have written the following code. This code is giving some wrong answers and also giving time limit exceed error . Can you tell what are the the mistakes present in my code ? where or what I am doing wrong here?

My code:

public static int downToZero(int n) {
// Write your code here
    int count1=0;
    int prev_i=0;
    int prev_j=0;
    int next1=0;
    int next2=Integer.MAX_VALUE;
    
    if (n==0){
        return 0;
    }

    while(n!=0){
        if(n==1){
            count1++;
            break;
        }
        next1=n-1;
        outerloop:
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                if (i*j==n){
                    if (prev_i ==j && prev_j==i){
                        break outerloop;
                    }
                    if (i !=j){
                        prev_i=i;
                        prev_j=j;
                    }
                    int max=Math.max(i,j);
                    if (max<next2){
                        next2=max;
                    }
                       
                }
                
            }
        }
        n=Math.min(next1,next2);
        count1++;
    }
    return count1;
}

This is part is coded for us:

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = Integer.parseInt(bufferedReader.readLine().trim());

        for (int qItr = 0; qItr < q; qItr++) {
            int n = Integer.parseInt(bufferedReader.readLine().trim());

            int result = Result.downToZero(n);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Ex: it is not working for number 7176 ….

Answer

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]