Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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;
}
#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()
#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) {
// 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;
}
}
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());
IntStream.range(0, q>.forEach(qItr -> {
try {
int n = Integer.parseInt(bufferedReader.readLine().trim());
int result = Result.downToZero(n);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
bufferedReader.close();
bufferedWriter.close();
}
}