## Algorithm

Problem Name: Data Structures - Down to Zero II

In this HackerRank in Data Structures - Balanced Brackets solutions

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

1: If we take 2 integers a and b where N = a * b(a not= 1, b not= 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 N to 0.

Input Format

The first line contains the integer Q.

The next Q lines each contain an integer, N.

Constraints

1 <= Q <= 10**3

0 <= N <= 10**6

Output Format

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

Sample Input

``````2
3
4
``````

Sample Output

``````3
3
``````

Explanation

For test case 1, We only have one option that gives the minimum number of moves.
Follow 3 -> 2 -> 1 -> 0,Hence 3 moves.

For the case 2, we can either go 4-> 3 -> 2 -> 1 -> 0 , or 4 -> 2 -> 1 -> .The 2nd option is more optimal. Hence, 3 moves.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>
using namespace std;

constexpr int N = 1'000'001;
static int dp[N];

void compute()
{
fill_n(dp, N, INT_MAX);

dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3;

for (int i = 1; i  <  N; ++i)
{
dp[i] = min(dp[i], 1 + dp[i - 1]);

for (int j = 1; j  < = i && j * i < N; ++j)
dp[j * i] = min(dp[j * i], dp[i] + 1);
}
}

int main()
{
compute();

ofstream fout(getenv("OUTPUT_PATH"));

int q; cin >> q;

while (q--)
{
int n; cin >> n;
fout << dp[n] << "\n";
}

return 0;
}
``````
Copy The Code &

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'downToZero' function below.
#
# The function is expected to return an INTEGER.
# The function accepts INTEGER n as parameter.
#

def downToZero(n):
a = n
list5=[]
def func1(a):
list1=[]
list2=[]
for i in range(a-1,1,-1):
if a%i==0:
b=[i]+[a//i]
b = sorted(b)
if b not in list1:
list1.append(b)
if len(list1) != 0:
for j in list1:
m = max(j)
list2.append(m)
d = min(list2)
return d
else:
return a-1

while True:
z = func1(a)
list5.append(z)
if z == 0:
break
elif z == -1:
list5=[]
break
else:
a = list5[-1]
continue
return len(list5)

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

q = int(input().strip())

for q_itr in range(q):
n = int(input().strip())

result = downToZero(n)

fptr.write(str(result) + '\n')

fptr.close()
``````
Copy The Code &

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

/*
* Complete the 'downToZero' function below.
*
* The function is expected to return an INTEGER.
* The function accepts INTEGER n as parameter.
*/

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;
}

}

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

IntStream.range(0, q>.forEach(qItr -> {
try {

int result = Result.downToZero(n);

bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});