# Down to Zero II

### Problem Statement :

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

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

Output Format

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

### Solution :

```                            ```Solution in C :

In C ++ :

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

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int test;
cin >> test;
while (test--){
int n ;
cin >> n ;
int steps = 0;
if (n==0){
cout << 0 << endl;
continue;
}
if (n==1){
cout << 1 << endl;
continue;
}
vector<int> dist(n+1,0);
queue<int> q;
q.push(n) ;
dist[n] = 1 ;
while (1){
int element = q.front();
q.pop();
if(element == 2){
cout << dist[2] + 1 << endl;
break ;
}
if (dist[element-1] == 0 ){
dist [element-1] = dist[element]+1;
q.push(element-1);
}
for (int i=2; i*i<=element; i++){
if (element%i == 0){
int maxfrac = element/i;
if (dist[maxfrac] == 0) dist [maxfrac] = dist[element] + 1, q.push(maxfrac);
}
}
}
}
return 0;
}

In Java :

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
private static int MAXSZ = (int)(1E6+1);
private static int[] dp;

private static int minimumMove(int n) {
if(n == 0) return 0;
if(dp[n] != -1) return dp[n];

int minMove = Integer.MAX_VALUE;
int sq = (int) Math.sqrt(n);

for(int i = 2; i <= sq; i++) {
if(n % i == 0) {
minMove = Math.min(minMove, 1+minimumMove(n/i));
}
}
minMove = Math.min(minMove, 1+ minimumMove(n-1));
return (dp[n] = minMove);
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

dp = new int[MAXSZ];
Arrays.fill(dp, -1);
dp[0] = 0; dp[1] = 1; dp[2] = 2;

int Q = sc.nextInt();
for(int q = 1; q <= Q; q++) {
int n = sc.nextInt();
System.out.println(minimumMove(n));
}
}
}

In C :

#include <stdio.h>
#include <stdio.h>
#include <string.h>
unsigned long long min(unsigned long long x, unsigned long long y);
unsigned long long ans[1000001];

int main(){
int Q,N,i,j;
memset(ans,-1,sizeof(ans));
ans[0]=0;
for(i=0;i<1000000;i++){
ans[i+1]=min(ans[i+1],ans[i]+1);
for(j=2;j<=i && i*(unsigned long long)j<1000001;j++)
ans[i*j]=min(ans[i*j],ans[i]+1);
}
scanf("%d",&Q);
while(Q--){
scanf("%d",&N);
printf("%llu\n",ans[N]);
}
return 0;
}
unsigned long long min(unsigned long long x, unsigned long long y){
return (x>y)?y:x;
}

In Python3 :

import math

import time
start = time.time()

def Sol( N ):
if N == 0: return 0
Q = [ (N,0) ]
setQ = [ 0 ] * N
while Q:
N, steps = Q.pop(0)
if N == 1: return steps+1
div = int(math.sqrt( N ))
while div > 1:
if N % div == 0 and not setQ[N // div]:
Q.append( (N // div, steps+1) )
setQ[ N // div ] = 1
div -= 1
if not setQ[N-1]:
Q.append( (N-1, steps+1) )
setQ[ N-1 ] = 1

Q = int(input())
for _ in range(Q):
N = int(input())
print(Sol(N))```
```

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty