Skip to content
Programming101
Programmingoneonone

Learn everything about programming

  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programmingoneonone

Learn everything about programming

HackerRank Down to Zero II problem solution

YASH PAL, 31 July 2024

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.

HackerRank Down to Zero II problem solution

Problem solution in Python programming.

import collections
lim = 10**6+1
dist = [0]*lim
active = collections.deque()
active.append(0)
while active:
   n = active.popleft()
   d = dist[n]+1
   x = n + 1
   if x < lim and dist[x] == 0:
      dist[x] = d
      active.append(x)
   for m in range(2,n+1):
      x = m * n
      if x >= lim: break
      if dist[x] == 0:
         dist[x] = d
         active.append(x)
Q = int(input())
for q in range(Q):
   N = int(input())
   print(dist[N])

Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {
  static int[] moves = new int[1000001];

  public static void main(String[] args) {
    for (int i = 1; i <= 1000000; ++i) {
      int least = moves[i - 1];
      for (int j = 2; j * j <= i; ++j) {
        if (i % j == 0) {
          least = Math.min(least, moves[i / j]);
        }
      }
      moves[i] = ++least;
    }
    Scanner in = new Scanner(System.in);
    int t = in.nextInt();
    while (t-- > 0) {
      System.out.println(moves[in.nextInt()]);
    }
  }
}

Problem solution in C++ programming.

#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define NSIZE 1000000

vector< vector<int> >  ar(NSIZE+1);

bool primes[NSIZE+1];
int cache[NSIZE], dcache[NSIZE];

void gen_primes()
{
	for (int i = 2; i <= NSIZE; i++) {

	}

	for (int i = 1; i <= NSIZE; i++) {
		bool prime = true;
		for (int j = 2; j*j<= i; j++) {
			if (i % j == 0) {
				prime = false;
				break;
			}
		}
		primes[i] = prime;
	}
}

void get_a(int n)
{
    if (primes[n])
        return;
    if (dcache[n] != -1)
        return;
    else
	dcache[n] = 1;

    for (int i = 2; i*i <= n; i++) {
        if (n % i == 0) {
            int v = n / i;
            if (v == 1 || i == 1)
                continue;
            v = v > i ? v : i;
	    ar[n].push_back(v);
        }
    }
}

int w[NSIZE];
void fill_cache(int steps, int number, int start)
{
    int indx = start;
    int st = 1;

    if (cache[start] != -1)
        st = cache[start] + 1;

    while(1) {
        int pos = w[indx];
        cache[pos] = st++;

        indx = pos;
        if (st == steps + 1)
            break;
    }
  }

int *q;
int qpos = 0;
int qend = 0;
int steps = 0;
int cal_steps(int v)
{
    for (int i = 0; i <= v; i++)
        w[i] = -1;

    qpos = 0;
    qend = 0;
    steps = 0;
    q[qend++] = v;
    q[qend++] = -1;

    while(1) {
	int val = q[qpos++];
	if (val == -1) {
		steps ++;
		q[qend++] = -1;
		val = q[qpos++];
	}

        if (val == 0) {
            return steps;
        }

	get_a(val);
        for (int i = 0; i < ar[val].size(); i++) {
            if (w[ar[val][i]] == -1)
                w[ar[val][i]] = val;
            int tmp_val = ar[val][i];
	    q[qend++] = tmp_val;
        }

	val -= 1;
	q[qend++] = val;
    }

    return -1;
}

int main() {
    std::ios_base::sync_with_stdio (false);
    q = new int[NSIZE * 19];
    int n, v;
    cin >> n;
	int max = n;
	for (int i = 0; i < NSIZE; i++) {
		cache[i] = -1;
		dcache[i] = -1;
	}
    gen_primes();
    while(n--) {
        cin >> v;
		if (v == 0) {
			cout << "0" << endl;
			continue;
		}
       cout << cal_steps(v) << endl;
    }
    return 0;
}

Problem solution in C programming.

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

#define N_MAX 1000001

int solns[N_MAX];

void initialize_solns() {
    for (int i = 0; i < N_MAX; i++) {
        solns[i] = 0;
    }
    solns[1] = 1;
    solns[2] = 2;
    solns[3] = 3;
    solns[4] = 3;
    // Actually solve
    for (int i = 1; i < N_MAX; i++) {
        if (!solns[i] || solns[i-1] + 1 < solns[i]) {
            solns[i] = solns[i-1] + 1;
        }
        for (int j = 1; j <= i && j * i < N_MAX; j++) {
            if (!solns[j*i] || solns[i] + 1 < solns[j*i]) {
                solns[j*i] = solns[i] + 1;
            }
        }
    }
}

int main() {
    initialize_solns();
    int Q; 
    scanf("%i", &Q);
    for(int a0 = 0; a0 < Q; a0++){
        int N; 
        scanf("%i", &N);
        printf("%dn", solns[N]);
    }
    return 0;
}

Problem solution in JavaScript programming.

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

var minCostMap = {0:0,1:1,2:2,3:3};
function getReductions(n){
    var sqrt = Math.floor(Math.sqrt(n));
    var reductions = [n-1];
    var r = 2;
    while(r<=sqrt){
        if(n%r===0){
           reductions.push(n/r);
        } 
        r++;
    }
    //console.log(reductions);
    return reductions;
}

function min(reductions){
    var minCost = Math.min();//infinity
    //console.log('reductions lenght: ',reductions.length);
    for(var i=reductions.length-1; i>=0; i--){
        var c = downToZero(reductions[i]);
        //console.log('c: ',c,' n:',reductions[i]);
        if(c<minCost){
           minCost=c;
        }
    }
    return minCost;
}

var minCostArray = [0,1,2,3];
function getMinCost(n){
    var reductions = getReductions(n);
    return min(reductions)+1;
}
function downToZero(n){
    var lastRecordedCost = minCostArray.length-1;
    if(n<=lastRecordedCost){
       return minCostArray[n];
    }
    
    while(n>lastRecordedCost){
        var nextCost = getMinCost(++lastRecordedCost);
        minCostArray.push(nextCost);
    }
    //console.log('minCostArray.lenght ',minCostArray.length);    
    //console.log('lastRecordedCost ',lastRecordedCost);
    //console.log(minCostArray);
    return minCostArray[lastRecordedCost];
}
/*
 * Complete the downToZero function below.
 */
function downToZero2(n) {
    /*
     * Write your code here.
     */
    if(minCostMap.hasOwnProperty(n)){
       return minCostMap[n];
    }else{
        var reductions = getReductions(n);
        var minCost = min(reductions) + 1;
        minCostMap[n] = minCost;
        return minCost;
    }
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const q = parseInt(readLine(), 10);

    for (let qItr = 0; qItr < q; qItr++) {
        const n = parseInt(readLine(), 10);

        let result = downToZero(n);

        ws.write(result + "n");
    }

    ws.end();
}

coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes