NPLQ18C : Wrong Answer

Problem Link : NPLQ18C Problem - CodeChef

Can anyone Help me with my solution for this question ? I went some correct submissions and checked output of correct submission and mine and both were same. So can anyone provide any failing test case for my solution ?

My solution : CodeChef: Practical coding for everyone

By going through your code, what I understood that is that you didn’t get the problem actually or maybe you failed to implement your idea correctly. Just for clarity, the problem asks for the next number greater than or equal to n, which is prime and lies in the range l to r. But what you have actually done in your code is that, you first found out the next prime number to n and then checked for something. No, you don’t need to find just the next prime to n, you need to find the next prime to n which lies in the range of l to r.

Since the given range of l to r is <= 1e5, you can use array to store all the prime numbers from l to r. Then you can use a dictionary to store the next prime numbers of the numbers in the range l to r, because the number between l and r are our concern. If n < l, then you simply need to print the next prime to l if it exists or print -1. If n > r or there is no prime number in after n which is < r, then simply print -1, otherwise you can find the prime number next to n within the given range of l to r from the dictionary in O(1) time, which is necessary for the large volume of queries.

You can find my solution if it help. :stuck_out_tongue:

Hope this clears your doubt about the solution. Feel free to ask if you have any more doubts. :smiley:

Actually what did is to find next prime greater than or equal to n and then store it in variable temp. Then I checked if temp lies in range l to r. If it does then I print temp else -1. This is just clarification. I found out what is wrong with my logic. Thanks for help. :slight_smile: