Problem

Submissions

Hints & solutions

Discuss

Fixed Point

Easy

0/40

Average time to solve is 15m

Contributed by

3 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1:

1
-1

Explanation of Sample Output 1:

In test case 1, 'ARR[1]' == 1, so you need to return 1.

In test case 2, No such value present, so you need to return -1.

Sample Input 2:

2
4
-1 0 2 4
5
-2 -1 0 1 2

Sample Output 2:

2
-1

Explanation of Sample Output 2:

In test case 1, 'ARR[2]' == 2, so you need to return 2.

In test case 2, No such value present, so you need to return -1.

Hint 1

Hint 2

Can you think of using Linear Search till ‘N’.

Approaches (2)

Approach 1

Approach 2

Linear Search

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

Time Complexity

O(N), Where ‘N’ is the length of the array

Since we are traversing through the complete array in the worst case, the overall time complexity will be O(N).

Space Complexity

O(1)

Since constant extra space is needed, so the overall space complexity will be O(1).

(100% EXP penalty)

Fixed Point

Console