We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The challenging part of this problem is actually understanding the ask from the author. If the question writer was perhaps more clear in expressing his intent, this would not be such a challenging problem.
Here's my attempt at the simple explanation of the problem. Hopefully I am more clear than the author.
Problem Statement:
Given a number n, dermine if it is a prime number.
If it is a prime number, decrement the number by 1, and this is next.
OR if it is not a prime number, find the 2 factors (a,b) of the number such that gives a > b, and a will be next. There are many a,b factors for n, but you want to chose the smallest a,b to give the fastest converge to 0. The ideal a,b set is where a=sqrt(n). If you cannot find a natural sqrt, then take the factor of "a" closest above the sqrt(n).
Continue to next as n, repeating #2 and #3 above choices until 0 is reached.
count the number of iterations it takes to get to 0.
Analysis:
2 ways to solve it: a. recurse backwards OR b. precompute forward and look up.
Because there can be 1000 queries and N is limited to 10^6 and the answer is fixed for each n. precompute is best since it will only take 10^6 integers.
So if you precompute and solve the simple n=4 and n=3 case, you will solve all the cases.
The precompute just works opposite from the recurse logic.
You do not have to compute primes, since a prime number is a number where the forward sweep will not update by the factor method, but rather by n-1.
Here's a my solution in C++
Hopefully it's clearer to read, and the debug printfs help undersand the solution.
To see the code work, uncomment the
#define DEBUG
... and test answers on a custom input where n < 25 or a small number to read so you can read the intent of the code.
//#define DEBUG#ifdef DEBUG#define MAX 25#define _printf printf#else#define MAX 1000000void_printf(...){}#endifintfind_max_multiple(intn){inti=n-1;inta,b;set<int>multiples;while(i>0){a=i;b=n/a;if(n%i==0){multiples.insert(max(a,b));}i--;}// n has factors, return lowest factor to get largest dropi=*(multiples.begin());// n is prime, return itselfif(multiples.size()==0){i=n;}returni;}voidprint_path(int*map,intn){inti=n;intnext=0;_printf("path for n %d [",n);while(i>0){if(i!=n){_printf(" %d ",i);}inta=find_max_multiple(i);if(map[i-1]<map[a]){next=i-1;}else{next=a;}i=next;}_printf("0]\n");}voidinit_map(int*map){intsqrt_max=sqrt(MAX);// init map with n=n-1 case, where no factor is consideredfor(inti=0;i<=MAX;i++){map[i]=i;}// update for n= (a*b where a>b and a of n=a*b) is next decrement stepfor(inti=1;i<MAX;i++){intscore=map[i]+1;_printf("eval i at map[%d] +1 = score %d\n",i,score);intlimit;// i+1 is a prime with no factors, while i is not prime and has// lower scoreif(map[i+1]>score){_printf("n-1 case map[%d+1]=%d>score=%d (i+1)=%d is a prime\n",i,map[i+1],score,i+1);map[i+1]=score;}// updating factors of i, updating those to the limit.if(i>sqrt_max){_printf("limiting i %d > sqrt_max %d max %d\n",i,sqrt_max,MAX);limit=MAX;}else{limit=i*i;_printf("limit %d = %d^2\n",limit,i);}_printf("looping j %d to set to the limit %d inc by i %d\n",i*2,limit,i);for(intj=i+i;j<=limit;j+=i){if(map[j]>score){_printf("a*b case map[%d] %d > score %d..saving smaller\n",j,map[j],score);map[j]=score;}}}#ifdef DEBUGfor(inti=0;i<MAX;i++){_printf("map[%d] %d\n",i,map[i]);}#endif }intmain(){ofstreamfout(getenv("OUTPUT_PATH"));intq;cin>>q;cin.ignore(numeric_limits<streamsize>::max(),'\n');intmap[MAX+1];init_map(map);for(intq_itr=0;q_itr<q;q_itr++){intn;cin>>n;cin.ignore(numeric_limits<streamsize>::max(),'\n');intresult=map[n];fout<<result<<"\n";#if DEBUG print_path(map,n);#endif }fout.close();return0;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Down to Zero II
You are viewing a single comment's thread. Return to all comments →
The challenging part of this problem is actually understanding the ask from the author. If the question writer was perhaps more clear in expressing his intent, this would not be such a challenging problem.
Here's my attempt at the simple explanation of the problem. Hopefully I am more clear than the author.
Problem Statement:
Analysis:
Here's a my solution in C++
Hopefully it's clearer to read, and the debug printfs help undersand the solution. To see the code work, uncomment the
#define DEBUG
... and test answers on a custom input where n < 25 or a small number to read so you can read the intent of the code.