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