# 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) {
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 {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

for (int qItr = 0; qItr < q; qItr++) {

int result = Result.downToZero(n);

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

bufferedWriter.close();
}
}
```

Ex: it is not working for number 7176 ….

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]
```