Down to Zero II

Question

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 1

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]