Home » Technical Interview Questions » Array Interview Questions » Find a Fixed Point in a Given Array

Find a Fixed Point in a Given Array


Reading Time - 2 mins

Given an array of n distinct elements, find a fixed point in a given array, where a fixed point means the element value is the same as the index.

Example

Input

5

arr[] = {0,4,8,2,9}

Output

0 is a fixed point in this array because value and index both are the same which is 0.

Input

6

arr[] = {2,7,9,3,10,8}

Output

3 is a fixed point in this array because value is 3 and index is 3.

Approach 1(Linear Search)

Here we traverse from start to end of the array and check the condition for the fixed point and if the condition is true then print the element and else print “No fixed point in the array“.

Algorithm

1. Till the end of the array, for each element
2. check if the element value is the same as the index value, If true print the element.

C++ Program for Find a Fixed Point in a Given Array

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N;
  cin>>N;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  for(int i = 0; i < N; i++)
    {
      if(arr[i] == i)
        {
          cout<<arr[i]<<endl;
          return 0;
        }
    }
  cout<<"No fixed point in the array \n";
  return 0;
}
5
1 2 1 3 5
3

Approach 2(Binary Search)

In this case, we can use the this approach for the sorted array. Apply a binary search and check the condition for a fixed point. If find such a position then print that element else print “No fixed point in the array”.

Algorithm

  1. Assign the low variable and high variable to the starting and end of the array
  2. Till low is less than high-
  3. First check if the middle element is a fixed point or not, if yes print the mid element.
    a. if the mid element value is less than the mid index. If yes, update low to mid +1
    b. if the mid element value is greater than the mid index. If yes, update high to mid -1

C++ Program for Find a Fixed Point in a Given Array

#include <bits/stdc++.h>
using namespace std;
int bin_search_fixed(int arr[],int low , int high)
{
  while(low <= high)
  {
    int mid = low + (high - low)/2;
    
    if(arr[mid] == mid)
      return mid;
    
    else if(arr[mid] < mid)
      low = mid +1;
    else
    high = mid - 1;  
    
  }
return -1;
}
int main()
{
  int N;
  cin>>N;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  int index = bin_search_fixed(arr,0,N-1);
  if(index >= 0)
    cout << arr[index]<<endl;
    
  else
    cout<<"No fixed point in the array \n";
  
  return 0;
}
5
1 2 1 6 5
No fixed point in the array

Complexity Analysis for Find a Fixed Point in a Given Array

Time Complexity

O(logn) where n is the size of the array. Here we use binary search which has logn time complexity.

Space Complexity

O(1) because we don’t use auxiliary space here.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions