Value Equal To The Index Value

Easy
0/40
Average time to solve is 15m
profile
Contributed by
24 upvotes
Asked in companies
AmazonHikeFactSet

Problem statement

Ninja and his friend are playing a game in which his friend selects an integer 'N'. He then picks 'N' random numbers and places them in an array/list ‘NUMARRAY’.

He asks Ninja to find all those numbers which are equal to their index values i.e. 'NUMARRAY[i]' = ‘i’ where ‘i’ ranges from 0 to 'N' - 1.

Can you help Ninja find all such numbers?

For example :

Let ‘NUMARRAY’ = [-4, -2, 2, 5]. Here, only 'NUMARRAY[2]' = 2. So, our answer is 2.

Note :

If there is no such number present in 'NUMARRAY,’ which equals its index value, 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 or queries to be run. Then the test cases follow.

The first line of each test case contains a single integer ‘N’.

The next line of each test case contains ‘N’ single space-separated integers denoting the numbers in ‘NUMARRAY.’.
Output Format : 
For each test case, print all the numbers which satisfy the given condition.

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

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints : 
1 <= ‘T’ <= 100
0 <= ‘N’ <= 5000
-5000 <= ‘NUMARRAY[i]’ <= 5000

Where 'T' denotes the number of test cases.
‘N’ is the number of elements in the array/list ‘NUMARRAY’.


Time Limit: 1 second
Sample Input 1 :
2
4
-4 -2 2 5
4
-4 -3 -2 -1
Sample Output 1:
2
-1

Explanation for Sample Output 1:

For sample test case 1: 
For ‘i’ = ‘0’, 'NUMARRAY[0]' = -4 which is not equal to index ‘i’, So we don’t include this number in our answer.
For ‘i’ = ‘1’ 'NUMARRAY[1]' = -2 which is not equal to index ‘i’, So we don’t include this number in our answer.
For ‘i’ = ‘2’ 'NUMARRAY[2]' = 2 which is equal to index ‘i’, So we include this number in our answer.
For ‘i’ = ‘3’ 'NUMARRAY[3]' = 5 which is not equal to index ‘i’, So we don’t include this number in our answer.

For sample test case 2: 
For ‘i’ = ‘0’ 'NUMARRAY[0]' = -4 which is not equal to index ‘i’, So we don’t include this number in our answer.
For ‘i’ = ‘1’ 'NUMARRAY[1]' = -3 which is not equal to index ‘i’, So we don’t include this number in our answer.
For ‘i’ = ‘2’ 'NUMARRAY[2]' = -2 which is not equal to index ‘i’, So we don’t include this number in our answer.
For ‘i’ = ‘3’ 'NUMARRAY[3]' = -1 which is not equal to index ‘i’, So we don’t include this number in our answer.
In this sample test case, we didn’t find any such index. So we return ‘-1’.
Sample Input 2 :
2
4
0 1 2 3
4
-1 1 2 5
Sample Output 2:
0 1 2 3
1 2

Explanation for Sample Output 2:

For sample test case 1: 
For ‘i’ = ‘0’ 'NUMARRAY[0]' = 0 which is equal to index ‘i’, So we include this number in our answer.
For ‘i’ = ‘1’ 'NUMARRAY[1]' = 1 which is equal to index ‘i’, So we include this number in our answer.
For ‘i’ = ‘2’ 'NUMARRAY[2]' = 2 which is equal to index ‘i’, So we include this number in our answer.
For ‘i’ = ‘3’ 'NUMARRAY[3]' = 3 which is equal to index ‘i’, So we include this number in our answer.


For sample test case 2: 
For ‘i’ = ‘0’ 'NUMARRAY[0]' = -1 which is not equal to index ‘i’, So we don’t include this number in our answer.
For ‘i’ = ‘1’ 'NUMARRAY[1]' = 1 which is equal to index ‘i’, So we include this number in our answer.
For ‘i’ = ‘2’ 'NUMARRAY[2]' = 2 which is equal to index ‘i’, So we include this number in our answer.
For ‘i’ = ‘3’ 'NUMARRAY[3]' = 5 which is not equal to index ‘i’, So we don’t include this number in our answer.
Hint

Apply Linear search.

Approaches (1)
Linear Search

We can simply iterate through the array for all the indices. If we find the number which is equal to its index value in ‘NUMARRAY’, we add this number into our answer.

 

Here is the algorithm :

  1. We declare a list/vector ‘allNumbers’ in which we store our answer.
  2. We run a loop for ‘i’ = ‘0’ to ‘N’:
    • If ‘NUMARRAY[i]’ equals to ‘i’:
      • Add ‘i’ to ‘allNumbers’.
  3. If ‘allNumbers.size()’ is equal to ‘0’
    • Add -1 to ‘allNumbers’ and then return ‘allNumbers’.
  4. Else return ‘allNumbers’.
Time Complexity

O(N)  Where ‘N’ is the number of elements in the array/list ‘NUMARRAY’.

 

For finding all the numbers which satisfy the given condition, we have to iterate once through ‘NUMARRAY’.

Space Complexity

O(N)

For storing elements that have a value equal to their index.

Code Solution
(100% EXP penalty)
Value Equal To The Index Value
Full screen
Console