Problem

Submissions

Hints & solutions

Discuss

Treasure Hunt

Easy

0/40

Contributed by

3 upvotes

Asked in companies

Problem statement

Alex and Rome are playing treasure hunting. Rome has a treasure box that Alex wants to open. Rome has N keys, each of which has a unique key number. She placed the keys in boxes numbered from 1 to N. Alex somehow cheated and came to know the key number that opens the treasure box. But he doesn’t know the box number which contains the key. Alex knows that for any box ‘i’ the key in the ith box has a key number greater than the key numbers of the keys placed in any box j where j<i.

Given a list of key numbers, help Alex find the box number which contains the key. Or report that Rome has not placed the correct key in any of the boxes.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer ‘T’, denoting the number of test cases. Then the test cases follow.

The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, denoting the number of boxes and the correct key number, respectively.

The second line of each test case contains  ‘N’ space-separated integers denoting the key numbers in the array ‘key’.

Output Format:

For each test case, Print the box number which contains the correct key or ‘-1’ if the key is not present.

Print the output of each test case in a new line.

Note:

You are not required to print the expected output. It has already been taken care of. Just implement the function.
It is guaranteed that key[i] > key[j] for all i>j.

Constraints:

1<= T <= 10
1 <= N <= 10^4
1 <= K <= 10^9
1 <= key[i] <= 10^9

Where ’T’ is the number of test cases, ‘N’ is the number of boxes, ‘K’ is the correct key number, and 'key[i]' is the key number of the key in the ith box.

Time Limit: 1 sec

Sample Input 1:

3
11 21
2 7 9 11 15 20 21 40 68 99 121
7 4
4 9 11 15 22 36 65 
4 10
1 2 3 4

Sample Output 1:

7
1
-1

Explanation for Sample Input 1:

In the first test case, there are 11 boxes with the key in every box as [2, 7, 9, 11, 15, 20, 21, 40, 68, 99, 121], and Alex needs to search the box with key number 21. As the 7th box contains the key with the key number 21. So, the answer is 7.
In the second test case, the array key is [4, 9, 11, 15, 22, 36, 65]. The 1st box contains the key with the key number 4. So, the answer is 1.
In the third test case, the array key is[1, 2, 3, 4]. No box contains a key with key number 10. Hence, the answer is -1.

Sample Input 2:

2
5 2
1 3 4 5 6
7 10
5 10 15 20 25 30 35

Sample Output 2:

-1
2

Hint 1

Hint 2

Hint 3

Can you check all the boxes to find the box with the correct key?

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

The idea here is to traverse the entire array ‘key’ linearly and find the box which contains the required key.

The steps are as follows:

We will initialize a variable ‘answer’ to -1.
Iterate from i = 0 to N - 1:
- If the current box contains the required key, then update ‘answer’ to the current index.
- We will start from the 1st box and iteratively move to the Nth box.
If there is no box with the required key, then ‘answer’ is already -1. So, we will return ‘answer’ as the final answer.

Time Complexity

O(N) where N is the number of boxes containing the keys Alex wants to open.

As we are checking every box, there are at most N iterations. Hence, the overall time complexity is O(N).

Space Complexity

O(1)

As we are not using any extra space. Hence, the overall space complexity is O(1).

(100% EXP penalty)

Treasure Hunt

Console