You are given an array A of length N. For any given integer X, you need to find an integer Z strictly greater than X such that Z is not present in the array A. You need to minimise the value of Z.
Input format :
First line : Two space seperated integers N and Q denoting the number of elements in array A and the number of queries respectively Second line : N space seperated integers denoting the array elements Next Q lines : Each line consists of an integer X Output fomat :
Print Q lines, each line denoting the answer to the corresponding query. Constraints :
Sample Input 5 2 2 7 5 9 15 3 9 Sample Output 4 10 Explanation For the first query, the minimum element greater than 3 and not present in the given array is 4. Similarly, for the second query, the answer is 10.
------------------------------------------------------------------------ for this problem i write this code
can anyone tell me where it is failing thanx in advance
If you want people to be able to help you should make some steps towards them.
Nobody wants to reconstruct solution ideas from solution code and then guess what bugs can occur here. Especially from code that is written in usual CP fashion with short and not self-explanatory (for people who are not familiar with your coding style) variable names and specific defines.
Now your post looks like roughly copy-pasted problem statement plus copy-pasted source code.
I am pretty sure if you will
people will definitely help you with your problem.
Thanks alot for your suggestion from next time i will take care all your considerations. I am explaning my logic-- since i have to find no. greater then x and that is not present in array, so if x+1, x+2, ... x+n presenting in array then x+n+1 will be ans so we have to first find consecutive substring starting from x+1 to x+n that is present in array so for this we apply binary search for finding it. why i choose binary search: arr = [11, 12, 13, 14, 15, 16] since consecutive substring (11 to 16) present in array so we can check it ... 16-11 == 5-0(index) so 11 to 16 is consecutive sequence so like this i check for substring starting from x+1 to x+n using binary search and once i get then x+n+1 will be ans.
Your approach seems to be fine overall. Probably a little bit overcomplicated though. But your implementation definitely misses some important parts:
Firstly, binary search is only applicable to sorted arrays. In your code I see no sorting, neither I see guarentee that input array is already sorted in statement. Try reordering elements in input data, and you will see answer changing. Consider test cases:
and
Secondly, your claim "if difference between elements is equal to difference between their indexes then all elements of subarray bounded between those elements are consecutive in natural order" is only true for sorted arrays of integers with no duplicates. Consider array
As you can see, array is already sorted and elements at indexes 0 and 5 have their difference equal to 6 - 1 = 5, but they do not form consequtive sequence.
Finally, I think, you need to improve your ability to test your solutions. Try generating corner cases that your solution may fail on or generate some random data and test your solution on it.
Good luck on catching out bugs.