Ninja and Infinite Size Array

Posted: 27 Feb, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

Ninja has been given an array/list ‘ARR’ of unknown size and an element ‘TARGET.’ The ‘ARR’ is sorted in ascending order and all the elements of the ‘ARR’ are different. However, the size of the array is unknown to you. So Ninja can only access the 'ARR' using an interface ‘readValueAtIndex’. If you are trying to access a value from the index not present in the ‘ARR,’ you get output ‘10 ^ 9 + 7’.Ninja has to find that the position of the element ‘TARGET’ if it is present in the ‘ARR’.

For example:

Let ‘ARR’ = {2 4 7 10}.

If you want to know that what is the value at the 0-index in ‘ARR’, use ‘readValueAtIndex(0)’. Then the output is 2.

Let’s assume that you are trying to get the value at the 10’th index so, use ‘readValueAtIndex(10)’. Then the output is ‘10 ^ 9 + 7’. Because you are trying to access an index that is greater than the size of ‘ARR’.

Note: If the element ‘TARGET’ is not present in the ‘ARR’ then return -1.

Input Format
The first line of input contains an integer ‘T’ which denotes the number of test cases. 

The first line of each test case contains a space-separated integer ‘N’ and ‘TARGET’, which represents the size of ‘ARR1’ and an element to be searched.

The next lines of each test case contain ‘N’ space-separated integers which represent the elements of ‘ARR1’.
Output Format :
For each test case, return the position of the element ‘TARGET’ if it is present in the ‘ARR’ otherwise return -1.

Output for each test case should be in a separate line.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= ‘T’ <= 100
1 <= ‘N’ <= 5000
1 <= ‘ARR1[i]’, ‘TARGET’ <= 100000

Where ‘ARR1[i]’ the element of the array 'ARR'.

Time Limit: 1 sec
Approach 1

As we know, all elements of ‘ARR’ are different. So, we can simply iterate through the ‘ARR’, and if ‘readValueAtIndex(i)’ equal to the ‘TARGET’. Then we return this position. If while traversing through the ‘ARR’ if we reach at the end of the ‘ARR’ then return -1.

 

The steps are as follows:

 

  1. We run a loop for ‘i ’= 0 to ‘readValueAtIndex(i) != 10^9+7:
    • If ‘readValueAtIndex(i)’ == ‘TARGET’:
      • Return ‘i’.
  2. Return -1.
Try Problem