Ninja and Infinite Size Array

Easy
0/40
Average time to solve is 15m
profile
Contributed by
3 upvotes
Asked in companies
Morgan StanleyDeutsche BankFlipkart limited

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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

Sample Input 1:

2
6 7
1 3 5 7 9 11
4 11
1 4 5 19

Sample Output 1:

3
-1

Explanation for Sample Output 1:

In test case 1, 7 is present in the ‘ARR’ at position 3 (0-based indexing). So the answer is 3.

In test case 2, 11 is not present in the ‘ARR’. So the answer is -1.

Sample Input 2:

2
5 4
4 6 13 17 19
5 19
1 4 5 10 19

Sample Output 2:

0
4

Explanation for Sample Output 2:

In test case 1, 4 is present in the ‘ARR’ at position 0 (0-based indexing). So the answer is 0.

In test case 2, 19 is present in the ‘ARR’ at position 4 (0-based indexing). So the answer is 4.
Hint

Think of Iterating each element in the array/list.

Approaches (2)
Linear Search

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.
Time Complexity

O(N),  Where ‘N’ is the number of elements in ‘ARR1’.

 

Since when an element is not present in the ‘ARR’ we have to traverse through the whole ‘ARR’. Thus the time complexity will be O(N).

Space Complexity

O(1).

 

Since we are not using any extra space for finding our resultant answer. Thus the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Ninja and Infinite Size Array
Full screen
Console