Fixed Point

Posted: 19 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given an array 'ARR' of ‘N’ distinct integers sorted in ascending order. You need to find the smallest fixed point in the array, such that the value stored at a particular index is equal to the index. That means 'ARR[i]' == 'i', where 'ARR[i]' denotes element at the the 'i'th index.

Note:
 1.Note that the array contains negative integers as well. 

2. Also, note that every array contains a single fixed point.
Example :
Given Array = [-1, 1, 3, 5]
In the above example 'ARR[1]' == 1, so you need to return 1.
Input Format:
The first line contains an integer ‘T’ which denotes the number of test cases. 

The first line of each test case contains a single integer ‘N’, denoting the size of the input array.

The next line contains ‘N’ space-separated integers denoting the elements of the array.
Output Format:
For each test case, you need to return a single integer denoting the index or value at which 'ARR[i]' == 1. In case no such value exists, return -1.

Print the output of each test case 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 <= 10
1 <=  N  <= 10000
-10^9 <= ARR[i] <= 10^9

Where 'ARR[i]' denotes element at the the 'i'th index.

Time limit: 1 sec
Approach 1

The basic approach will be to traverse through the array checking for each value and once you come to a value that satisfies the condition ‘ARR[i]’ == ‘i’, simply print the value of i.

 

The steps are as follows:

 

  • Start traversing through the array:
    • Check if ‘ARR[i]' == 'i':
      • YES:
        • Return ‘i’
        • break
      • NO:
        • continue
Try Problem