Down to Zero II

Problem : https://www.hackerrank.com/challenges/down-to-zero-ii


You are given queries. Each query consists of a single number N. You can perform 2 operations on N in each move.

If N=a*b (a!=1,b!=1),we can change N= max(a,b) or 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 lines each contain an integer, N.


Constraints:


1 ≤ Q ≤ 103

0 ≤ N ≤ 106

```
#include
using namespace std;

#define SIZE 1000000

//O(nloglogn)
//Sieve of Eratosthenes

void getPrimes(vector &prime){
for(long i=2;i*i=2;i--){
if(n%i==0){
res = (n/i);
break;
}
}
return res;
}

//Try BFS

long solve(long n,long z, vector &prime,unordered_map &map){
long result=LLONG_MAX;
long s,tmp;

queue> q;

if(map.find(n)!=map.end())
result= map[n];
else{
q.push(make_pair(n,0));
while(!q.empty()){

pair p = q.front(); q.pop();
n = p.first;
s = p.second;

if(!n){
result = min(result,s);
break;
}
else if(map.find(n)!=map.end()){
result = min(result,s+map[n]);
}
else{

//Push (n-1) in queue.
q.push(make_pair(n-1,1+s));

//If n is not prime insert 'max(a,b)' in queue.
if(!prime[n]){
tmp = getVal(n);
q.push(make_pair(tmp,s+1));
}

}
}
}

return map[z]=result;
}

int main() {

vector prime(SIZE,true);
getPrimes(prime);

unordered_map map;
for(long i=0;i>queries;
while(queries--){
cin>>n;
cout<<solve(n,n,prime,map)<<endl;
}

Bug

Your code assumes that the minimum factor pair out of all factor pairs is best. For example, if n=36, it chooses 6 from (6,6) instead of 9 from (4,9), 12 from (3,12), or 18 from (2,18) because 6 is the smallest of the max(a,b) factors.

However, this may not give you the optimal solution. Consider the case n = 60. Your code finds the following answer:

60 -> 10 -> 5 -> 4 -> 2 -> 1 -> 0 (length 7 chain)

Note that it chose 10 from (6,10). The optimal solution is:

60 -> 12 -> 4 -> 2 -> 1 -> 0 (length 6 chain)

To find this solution, you must consider other factors such as 12 from (5,12).
Memoization unused

Your program attempts to use memoization via the map variable, but doesn't utilize map enough. Given your example of n=300, the function searches through thousands of possibilities without even once writing any result to the map variable until the very end, and then only for map[300]. What it should do is write the results for each of the factors as it recursively finds the solution for them. That way you never need to find the answer to the same number twice.
Faster way

A faster way would be to solve for each number up to the maximum (1000000). Then for each query you would just need to look up the answer in the map. Here is how I would do it:

#include 
#include 

#define MAX     1000000

int map[MAX+1];

int main(void)
{
    int numCases = 0;
    int i        = 0;
    int n        = 0;
    int sqrt_max = sqrt(MAX);

    // Init map to worst case scenario.
    for (int i=0; i  score)
            map[i+1] = score;
        // Handler the k*i case.  We start at 2*i, and go up until i*i, but
        // not more than MAX.
        if (i > sqrt_max)
            limit = MAX;
        else
            limit = i*i;
        for (int j = i+i; j  score)
                map[j] = score;
        }
    }

    // At this point, map contains all the best solutions.
    if (scanf("%d", &numCases) != 1)
        return 1;
    while (numCases-- > 0) {
        scanf("%d", &n);
        printf("%d\n", map[n]);
    }
    return 0;
}

This program was able to compute all solutions in 0.02 seconds.

StackExchange Code Review Q#142119, answer score: 2