HackerRank Down to Zero II problem solution

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.

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();
}