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 <bits/stdc++.h>
using namespace std;
#define SIZE 1000000
//O(nloglogn)
//Sieve of Eratosthenes
void getPrimes(vector<bool> &prime){
for(long i=2;i*i<=SIZE;i++)
if(prime[i])
for(long j=i*i;j<SIZE;j+=i)
prime[j]=0;
}
//O(sqrt(n))
//Get 'max(a,b)' as defined in the problem
//input n is always non-prime
long getVal(long n){
long res;
for(long i=sqrt(n);i>=2;i--){
if(n%i==0){
res = (n/i);
break;
}
}
return res;
}
//Try BFS
long solve(long n,long z, vector<bool> &prime,unordered_map<long ,long> &map){
long result=LLONG_MAX;
long s,tmp;
queue<pair<long,long>> q;
if(map.find(n)!=map.end())
result= map[n];
else{
q.push(make_pair(n,0));
while(!q.empty()){
pair<long,long> 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<bool> prime(SIZE,true);
getPrimes(prime);
unordered_map<long ,long> map;
for(long i=0;i<=3;i++) map[i]=i;
int queries,n;
cin>>queries;
while(queries--){
cin>>n;
cout<<solve(n,n,prime,map)<<endl;
}
return 0;
}
I have implemented the following optimizations:
Precomputed primes.
Getting the required 'max(a,b)' in optimal possible way.
Storing the solutions to the sub-problems.
How can I optimize it further for it to be accepted? (Though it is about writing code in competitive programming,I will be happy if you also provide suggestions to improve the readability of code and overall coding style to make it a production level code.)
max(a,b)
be 6? Or can a=3,b=4 andmax(a,b)
be 4? In other words, can you choose from many different factors, or not? The wording in the problem isn't very clear on this point. I see your program assumes that you can only choose the largest of all factors. I checked the discussion on the hackerrank problem and it seems to imply that you can choose from multiple factors, not just the largest. \$\endgroup\$