Last Updated: 19 Mar, 2021

Fixed Point

Easy

Asked in companies

Solve now

Problem statement

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

Solve now

Approaches

01 Approach

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

Solve now

02 Approach

A better approach would be to use the concept of Binary Search. We know that the array is already sorted. So, if we know that the middle element is greater than the index it is stored on, we can assume that the fixed point will be on the right side of the middle element and similarly for the other side.

Example:

‘ARR’ = [-1, 0, 1, 3, 4]

‘MID’ element = 1, we know 1 < 2 (index at which it is stored), and as the array is sorted, we also know that there can’t be any value before 1, which can be equal to its index. To verify, 0 < 1 and -1 < 0.

So, we update ‘LOW’ with ‘MID’ + 1, and check in the right side of ‘MID’.

New ‘MID’ = 3, and we found that 3 = 3 (index it is stored on), so return 3.

Taking another example in which we would require to move to left side:

‘ARR’ = [0, 2, 3, 4, 5]

‘MID’ element = 3, which is greater than the index it is stored on(2), and similarly as the array is sorted, we also know that there can’t be any value after 3, which can be equal to its index. To verify, 4 > 3 and 5 > 4.

So, update ‘HIGH’ with ‘MID’ - 1, and check the left side of ‘MID’.

New ‘MID’ = 2, which is greater than the index it is stored on(1), ao again move to the left side.

New ‘MID’ = 0, which is equal to index it is stored on(0), so you need to return 0.

The steps are as follows:

Find the middle element of the array and check if it is the fixed point: ‘ARR[MID]’ == ‘MID’:
- If yes :
  - Return ‘MID’
- Else check if ‘MID’ > 'ARR[MID]':
  - Apply binary search in the right part
- Else check if ‘MID’ < 'ARR[MID]'
  - Apply binary search in the left part

Solve now