Find fixed point in array

Given an array of integers, the task is to write a program that finds and prints any fixed point in the array. A fixed point is an index i where the value at that index is equal to i. If no fixed point exists in the array, an appropriate message is displayed.

Example

Consider the following examples of arrays:

1. Array: [8, 3, 1, 6, 4]

   • Here, the fixed point is 4 since arr[4] is equal to 4.

2. Array: [4, 2, 7, 9, 2, 9, 1]

   • There is no fixed point in this array.

3. Array: [4, 1, 7, 9, 2, 5, 1]

   • Here, the fixed point is 1 since arr[1] is equal to 1.

Idea to Solve the Problem

To solve this problem, we can follow these steps:

1. Iterate through the array and compare each element with its index.
2. If an element is equal to its index, that index is a fixed point.
3. If no fixed point is found after iterating through the entire array, then there is no fixed point.

Standard Pseudocode

Here's a high-level pseudocode representation of the algorithm to find a fixed point in an array:

FindFixedPoint(arr, size):
    Initialize location to -1
    
    For i from 0 to size-1:
        If arr[i] equals i:
            Set location to i
            Break the loop
    
    Display the array elements
    If location is -1:
        Display "Fixed point not exists"
    Else:
        Display "Fixed point is", location

Algorithm Explanation

1. Initialize location to -1.
2. Iterate through the array using a loop that goes from 0 to size-1.
3. For each index i, check if the element arr[i] is equal to i.
4. If the condition is met, set location to i and break the loop.
5. Display the array elements.
6. If location is still -1, it means no fixed point was found. Display "Fixed point not exists."
7. If location is not -1, display "Fixed point is" followed by the value of location.

Code Solution

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

// C Program 
// Find fixed point in array
#include <stdio.h>

//Function which is display array elements
void display(int arr[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
// Find the fixed point in array
void find_fixed_point(int arr[], int size)
{
	int location = -1;
	for (int i = 0; i < size && location == -1; ++i)
	{
		if (i == arr[i])
		{
			//When get fixed point
			location = i;
		}
	}
	printf("\n Array element : ");
	display(arr, size);
	if (location == -1)
	{
		//When no fixed point exists
		printf(" Fixed point not exists\n");
	}
	else
	{
		printf(" Fixed point is %d\n", location);
	}
}
int main()
{
	int arr1[] = {
		8 , 3 , 1 , 6 , 4
	};
	//Get the size of array
	int size = sizeof(arr1) / sizeof(arr1[0]);
	find_fixed_point(arr1, size);
	int arr2[] = {
		4 , 2 , 7 , 9 , 2 , 9 , 1
	};
	//Get the size of array
	size = sizeof(arr2) / sizeof(arr2[0]);
	find_fixed_point(arr2, size);
	//When more than 2 fixed point exist
	int arr3[] = {
		4 , 1 , 7 , 9 , 2 , 5 , 1
	};
	//Get the size of array
	size = sizeof(arr3) / sizeof(arr3[0]);
	find_fixed_point(arr3, size);
	return 0;
}

 Array element : 8 3 1 6 4
 Fixed point is 4

 Array element : 4 2 7 9 2 9 1
 Fixed point not exists

 Array element : 4 1 7 9 2 5 1
 Fixed point is 1

// Java Program
// Find fixed point in array
class MyArray
{
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			System.out.print(" " + arr[i]);
		}
		System.out.print("\n");
	}
	// Find the fixed point in array
	public void find_fixed_point(int[] arr, int size)
	{
		int location = -1;
		for (int i = 0; i < size && location == -1; ++i)
		{
			if (i == arr[i])
			{
				//When get fixed point
				location = i;
			}
		}
		System.out.print("\n Array element : ");
		display(arr, size);
		if (location == -1)
		{
			System.out.print(" Fixed point not exists\n");
		}
		else
		{
			System.out.print(" Fixed point is " + location + "\n");
		}
	}
	public static void main(String[] args)
	{
		MyArray obj = new MyArray();
		int[] arr1 = {
			8 , 3 , 1 , 6 , 4
		};
		//Get the size of array
		int size = arr1.length;
		obj.find_fixed_point(arr1, size);
		int[] arr2 = {
			4 , 2 , 7 , 9 , 2 , 9 , 1
		};
		//Get the size of array
		size = arr2.length;
		obj.find_fixed_point(arr2, size);
		//When more than 2 fixed point exist
		int[] arr3 = {
			4 , 1 , 7 , 9 , 2 , 5 , 1
		};
		//Get the size of array
		size = arr3.length;
		obj.find_fixed_point(arr3, size);
	}
}

 Array element :  8 3 1 6 4
 Fixed point is 4

 Array element :  4 2 7 9 2 9 1
 Fixed point not exists

 Array element :  4 1 7 9 2 5 1
 Fixed point is 1

//Include header file
#include <iostream>

using namespace std;
// C++ Program
// Find fixed point in array
class MyArray
{
	public:
		//Function which is display array elements
		void display(int arr[], int size)
		{
			for (int i = 0; i < size; ++i)
			{
				cout << " " << arr[i];
			}
			cout << "\n";
		}
	// Find the fixed point in array
	void find_fixed_point(int arr[], int size)
	{
		int location = -1;
		for (int i = 0; i < size && location == -1; ++i)
		{
			if (i == arr[i])
			{
				//When get fixed point
				location = i;
			}
		}
		cout << "\n Array element : ";
		this->display(arr, size);
		if (location == -1)
		{
			cout << " Fixed point not exists\n";
		}
		else
		{
			cout << " Fixed point is " << location << "\n";
		}
	}
};
int main()
{
	MyArray obj = MyArray();
	int arr1[] = {
		8 , 3 , 1 , 6 , 4
	};
	//Get the size of array
	int size = sizeof(arr1) / sizeof(arr1[0]);
	obj.find_fixed_point(arr1, size);
	int arr2[] = {
		4 , 2 , 7 , 9 , 2 , 9 , 1
	};
	//Get the size of array
	size = sizeof(arr2) / sizeof(arr2[0]);
	obj.find_fixed_point(arr2, size);
	int arr3[] = {
		4 , 1 , 7 , 9 , 2 , 5 , 1
	};
	//Get the size of array
	size = sizeof(arr3) / sizeof(arr3[0]);
	obj.find_fixed_point(arr3, size);
	return 0;
}

 Array element :  8 3 1 6 4
 Fixed point is 4

 Array element :  4 2 7 9 2 9 1
 Fixed point not exists

 Array element :  4 1 7 9 2 5 1
 Fixed point is 1

//Include namespace system
using System;
// C# Program
// Find fixed point in array
class MyArray
{
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	// Find the fixed point in array
	public void find_fixed_point(int[] arr, int size)
	{
		int location = -1;
		for (int i = 0; i < size && location == -1; ++i)
		{
			if (i == arr[i])
			{
				//When get fixed point
				location = i;
			}
		}
		Console.Write("\n Array element : ");
		display(arr, size);
		if (location == -1)
		{
			Console.Write(" Fixed point not exists\n");
		}
		else
		{
			Console.Write(" Fixed point is " + location + "\n");
		}
	}
	public static void Main(String[] args)
	{
		MyArray obj = new MyArray();
		int[] arr1 = {
			8 , 3 , 1 , 6 , 4
		};
		//Get the size of array
		int size = arr1.Length;
		obj.find_fixed_point(arr1, size);
		int[] arr2 = {
			4 , 2 , 7 , 9 , 2 , 9 , 1
		};
		//Get the size of array
		size = arr2.Length;
		obj.find_fixed_point(arr2, size);
		int[] arr3 = {
			4 , 1 , 7 , 9 , 2 , 5 , 1
		};
		//Get the size of array
		size = arr3.Length;
		obj.find_fixed_point(arr3, size);
	}
}

 Array element :  8 3 1 6 4
 Fixed point is 4

 Array element :  4 2 7 9 2 9 1
 Fixed point not exists

 Array element :  4 1 7 9 2 5 1
 Fixed point is 1

<?php
// Php Program
// Find fixed point in array
class MyArray
{
	//Function which is display array elements
	public	function display( $arr, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo " ". $arr[$i];
		}
		echo "\n";
	}
	// Find the fixed point in array
	public	function find_fixed_point( $arr, $size)
	{
		$location = -1;
		for ($i = 0; $i < $size && $location == -1; ++$i)
		{
			if ($i == $arr[$i])
			{
				//When get fixed point
				$location = $i;
			}
		}
		echo "\n Array element : ";
		$this->display($arr, $size);
		if ($location == -1)
		{
			echo " Fixed point not exists\n";
		}
		else
		{
			echo " Fixed point is ". $location ."\n";
		}
	}
}

function main()
{
	$obj = new MyArray();
	$arr1 = array(8, 3, 1, 6, 4);
	//Get the size of array
	$size = count($arr1);
	$obj->find_fixed_point($arr1, $size);
	$arr2 = array(4, 2, 7, 9, 2, 9, 1);
	//Get the size of array
	$size = count($arr2);
	$obj->find_fixed_point($arr2, $size);
	//When more than 2 fixed point exist
	$arr3 = array(4, 1, 7, 9, 2, 5, 1);
	//Get the size of array
	$size = count($arr3);
	$obj->find_fixed_point($arr3, $size);
}
main();

 Array element :  8 3 1 6 4
 Fixed point is 4

 Array element :  4 2 7 9 2 9 1
 Fixed point not exists

 Array element :  4 1 7 9 2 5 1
 Fixed point is 1

// Node Js Program
// Find fixed point in array
class MyArray
{
	//Function which is display array elements
	display(arr, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	// Find the fixed point in array
	find_fixed_point(arr, size)
	{
		var location = -1;
		for (var i = 0; i < size && location == -1; ++i)
		{
			if (i == arr[i])
			{
				//When get fixed point
				location = i;
			}
		}
		process.stdout.write("\n Array element : ");
		this.display(arr, size);
		if (location == -1)
		{
			process.stdout.write(" Fixed point not exists\n");
		}
		else
		{
			process.stdout.write(" Fixed point is " + location + "\n");
		}
	}
}

function main()
{
	var obj = new MyArray();
	var arr1 = [8, 3, 1, 6, 4];
	//Get the size of array
	var size = arr1.length;
	obj.find_fixed_point(arr1, size);
	var arr2 = [4, 2, 7, 9, 2, 9, 1];
	//Get the size of array
	size = arr2.length;
	obj.find_fixed_point(arr2, size);
	//When more than 2 fixed point exist
	var arr3 = [4, 1, 7, 9, 2, 5, 1];
	//Get the size of array
	size = arr3.length;
	obj.find_fixed_point(arr3, size);
}
main();

 Array element :  8 3 1 6 4
 Fixed point is 4

 Array element :  4 2 7 9 2 9 1
 Fixed point not exists

 Array element :  4 1 7 9 2 5 1
 Fixed point is 1

#  Python 3 Program
#  Find fixed point in array
class MyArray :
	# Function which is display array elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	
	#  Find the fixed point in array
	def find_fixed_point(self, arr, size) :
		location = -1
		i = 0
		while (i < size and location == -1) :
			if (i == arr[i]) :
				# When get fixed point
				location = i
			
			i += 1
		
		print("\n Array element : ", end = "")
		self.display(arr, size)
		if (location == -1) :
			print(" Fixed point not exists\n", end = "")
		else :
			print(" Fixed point is ", location ,"\n", end = "")
		
	

def main() :
	obj = MyArray()
	arr1 = [8, 3, 1, 6, 4]
	# Get the size of array
	size = len(arr1)
	obj.find_fixed_point(arr1, size)
	arr2 = [4, 2, 7, 9, 2, 9, 1]
	# Get the size of array
	size = len(arr2)
	obj.find_fixed_point(arr2, size)
	# When more than 2 fixed point exist
	arr3 = [4, 1, 7, 9, 2, 5, 1]
	# Get the size of array
	size = len(arr3)
	obj.find_fixed_point(arr3, size)

if __name__ == "__main__": main()

 Array element :   8  3  1  6  4
 Fixed point is  4

 Array element :   4  2  7  9  2  9  1
 Fixed point not exists

 Array element :   4  1  7  9  2  5  1
 Fixed point is  1

#  Ruby Program
#  Find fixed point in array
class MyArray

	# Function which is display array elements
	def display(arr, size)
	
		i = 0
		while (i < size)
		
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
	#  Find the fixed point in array
	def find_fixed_point(arr, size)
	
		location = -1
		i = 0
		while (i < size && location == -1)
		
			if (i == arr[i])
			
				# When get fixed point
				location = i
			end
			i += 1
		end
		print("\n Array element : ")
		self.display(arr, size)
		if (location == -1)
		
			print(" Fixed point not exists\n")
		else
		
			print(" Fixed point is ", location ,"\n")
		end
	end
end
def main()

	obj = MyArray.new()
	arr1 = [8, 3, 1, 6, 4]
	# Get the size of array
	size = arr1.length
	obj.find_fixed_point(arr1, size)
	arr2 = [4, 2, 7, 9, 2, 9, 1]
	# Get the size of array
	size = arr2.length
	obj.find_fixed_point(arr2, size)
	# When more than 2 fixed point exist
	arr3 = [4, 1, 7, 9, 2, 5, 1]
	# Get the size of array
	size = arr3.length
	obj.find_fixed_point(arr3, size)
end
main()

 Array element :  8 3 1 6 4
 Fixed point is 4

 Array element :  4 2 7 9 2 9 1
 Fixed point not exists

 Array element :  4 1 7 9 2 5 1
 Fixed point is 1

// Scala Program
// Find fixed point in array
class MyArray
{
	//Function which is display array elements
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	// Find the fixed point in array
	def find_fixed_point(arr: Array[Int], size: Int): Unit = {
		var location: Int = -1;
		var i: Int = 0;
		while (i < size && location == -1)
		{
			if (i == arr(i))
			{
				//When get fixed point
				location = i;
			}
			i += 1;
		}
		print("\n Array element : ");
		display(arr, size);
		if (location == -1)
		{
			print(" Fixed point not exists\n");
		}
		else
		{
			print(" Fixed point is " + location + "\n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyArray = new MyArray();
		var arr1: Array[Int] = Array(8, 3, 1, 6, 4);
		//Get the size of array
		var size: Int = arr1.length;
		obj.find_fixed_point(arr1, size);
		var arr2: Array[Int] = Array(4, 2, 7, 9, 2, 9, 1);
		//Get the size of array
		size = arr2.length;
		obj.find_fixed_point(arr2, size);
		//When more than 2 fixed point exist
		var arr3: Array[Int] = Array(4, 1, 7, 9, 2, 5, 1);
		//Get the size of array
		size = arr3.length;
		obj.find_fixed_point(arr3, size);
	}
}

 Array element :  8 3 1 6 4
 Fixed point is 4

 Array element :  4 2 7 9 2 9 1
 Fixed point not exists

 Array element :  4 1 7 9 2 5 1
 Fixed point is 1

// Swift Program
// Find fixed point in array
class MyArray
{
	//Function which is display array elements
	func display(_ arr: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
	// Find the fixed point in array
	func find_fixed_point(_ arr: [Int], _ size: Int)
	{
		var location: Int = -1;
		var i: Int = 0;
		while (i < size && location == -1)
		{
			if (i == arr[i])
			{
				//When get fixed point
				location = i;
			}
			i += 1;
		}
		print("\n Array element : ", terminator: "");
		self.display(arr, size);
		if (location == -1)
		{
			print(" Fixed point not exists\n", terminator: "");
		}
		else
		{
			print(" Fixed point is ", location ,"\n", terminator: "");
		}
	}
}
func main()
{
	let obj: MyArray = MyArray();
	let arr1: [Int] = [8, 3, 1, 6, 4];
	//Get the size of array
	var size: Int = arr1.count;
	obj.find_fixed_point(arr1, size);
	let arr2: [Int] = [4, 2, 7, 9, 2, 9, 1];
	//Get the size of array
	size = arr2.count;
	obj.find_fixed_point(arr2, size);
	//When more than 2 fixed point exist
	let arr3: [Int] = [4, 1, 7, 9, 2, 5, 1];
	//Get the size of array
	size = arr3.count;
	obj.find_fixed_point(arr3, size);
}
main();

 Array element :   8  3  1  6  4
 Fixed point is  4

 Array element :   4  2  7  9  2  9  1
 Fixed point not exists

 Array element :   4  1  7  9  2  5  1
 Fixed point is  1

Time Complexity

The time complexity of finding a fixed point in an array using the provided algorithm is O(n), where 'n' is the number of elements in the array. In the worst case, the algorithm may need to iterate through the entire array to find a fixed point.