Prateek Loves Candy

#1

Can someone pls explain how to do this problem?

#2

hi @anugrahrastogi
Main logic behind the question is that you need to find the nth prime number starting from 2. Any one can implement this logic “Not a big Deal” for anyone, but wait a min there’s more to it.

Many of you are getting time limit exceed right ? Even if you are using SOE (Sieve of Eratosthenes) for finding the prime numbers.

Have u see the constraint on number of test cases, It’s quite large because for every test case you are going to find the prime numbers upto that number and at last return the last prime number found, this will cause the TLE for big test cases.

So, to overcome this problem, let’s just store your test cases in an array.
Then find the maximum number from all of the testcases.
then, Use SOE(Sieve of Eratosthenes) to find the prime number upto that number and store that an the array.
After storing, simply loop over every test case that was stored previously in an array.
Print the value of n from the array storing primes.
That’s how we need not to find the prime number for every test case. :slight_smile:

#3

What is Sieve of Eratosthenes?

#4

@anugrahrastogi
it is a way of storing prime numbers upto a given range.
you can read about it online if you still didn’t get it i will explain you with example

#5

I have written the code in python as I am not familiar with arrays in java. But last test case failed and shows TLE. What could be the reason?

#6

@anugrahrastogi
in order to use SOE you should have the basic understanding of arrays.If you use any other method then you will get TLE for sure!

#7

I have used SOE using arrays in python, but still it is showing TLE

#8

@anugrahrastogi
you can send me your code i ll have a look

#9
#10

@anugrahrastogi
what you can do to improve time complexity you can calculate the the maximum value of n
then create a list of size maximum and add all the element from 1 to maximum in the list.
then instead of calculate the value of each n you can directly print the value of n from the list .

if you have doubt i can explain you with the example.

#11

Can you pls explain with example?

#12

for eg;
10

999
981
1000
900
800
700
699
555
678
921

now instead of solving for each value of n you can just solve for n=1000
and create a list of size 1000 let suppose arr
so when ever you count is equal to i<=1000 you store that prime value in ith index of arr.

arr[]={2,3,5,7,11,13,…}
if you want the ans for any value of n let suppose n=800 for this you ans will be present at index i=799 of arraylist arr.

I hope this will help you understand it better .:blush:

#13

Thank you sooo much, just because of your help I was able to solve the problem!!!

#14

@anugrahrastogi
please mark your doubt as resolved in my doubts section and rate me as well(additional feedback will be much appreciated) :blush::blush: