Down to zero ii hackerrank solution

Down to Zero II, is a HackerRank problem from Queues subdomain. In this post we will see how we can solve this challenge in Python

Problem Description

You are given queries. Each query consists of a single number . You can perform any of the operations on in each move: 1: If we take 2 integers and where , , then we can change

2: Decrease the value of by .

Determine the minimum number of moves required to reduce the value of to .

Input F ....

You can find the full details of the problem Down to Zero II at HackerRank

Solution: Please check the down-to-zero-ii.py snippet for the solution.

This solution originally posted at: Github by @srgnk

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))

In this HackerRank Down to Zero II problem, we have given Q queries. each query consists of a single number N. we need to determine the minimum number of moves required to reduce the value of N to 0 after performing operations on N.

Problem solution in Python programming.

Problem solution in Java Programming.

Problem solution in C++ programming.

Problem solution in C programming.

Problem solution in JavaScript programming.