### singh1495's blog

By singh1495, history, 4 years ago,

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

https://ideone.com/x5LZfC

can anyone tell me where it is failing thanx in advance

• -18

 » 4 years ago, # |   0 Auto comment: topic has been updated by singh1495 (previous revision, new revision, compare).
•  » » » 4 years ago, # ^ |   +1 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: 5 5 1 2 3 4 5 1 2 3 4 5 and 5 5 5 4 3 2 1 1 2 3 4 5 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 1 2 2 5 5 6 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.