singh1495's blog

interesting twist
By singh1495, history, 6 years ago, In English

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

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  1. make problem statement well-formatted and complete (now "Constraints" section seems to be completely missing) or even better — provide a link for original statement instead
  2. describe the idea behind your solution — what are you trying to do, step by step
  3. give some comments about your solution code — what do you store in most important variables, which parts of your code execute which steps of your solution idea

people will definitely help you with your problem.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply