All Tracks Algorithms Searching Binary Search Problem

Sherlock and Numbers
Tag(s):

Binary search algorithm, Easy, Sorting algorithm

Problem
Editorial
Analytics

Watson gives to Sherlock a bag of numbers [1, 2, 3 ... N] and then he removes K numbers A1, A2 ... AK from the bag. He now asks Sherlock to find the P'th smallest number in the bag.

Input
First line contains T, the number of test cases. Each test case consists of N, K and P followed by K integers in next line denoting the array A.

Output
For each test case, print P'th smallest number in the bag. If no such number exists output -1.

Constraints
1 ≤ T ≤ 10
20% testdata: 1 ≤ N ≤ 103
20% testdata: 1 ≤ N ≤ 105
60% testdata: 1 ≤ N ≤ 109
0 ≤ Kmin(N, 105)
1 ≤ PN

Note: Large input files. Use scanf instead of cin.

SAMPLE INPUT
2
4 1 2
1
5 2 4
1 3
SAMPLE OUTPUT
3
-1
Explanation

Test case 1: Remaining numbers are [2, 3, 4]. 3 is the 2nd smallest remaining numbers.

Test case 2: Remaining numbers are [2, 4, 5]. 4th smallest remaining number doesn't exist.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

February Love '15

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?