Algorithm


Problem Name: Data Structures - Down to Zero II

Problem Link: https://www.hackerrank.com/challenges/down-to-zero-ii/problem?isFullScreen=true

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 & Try With Live Editor

#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 & Try With Live Editor

#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();
    }
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Castle on the Grid solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Game of Two Stacks solution in Hackerrank - Hacerrank solution C, C++, java,js, Python