Posted on by Kalkicode
Code Array

# 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` 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` 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 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);
find_fixed_point(arr1, size);
int arr2[] = {
4 , 2 , 7 , 9 , 2 , 9 , 1
};
//Get the size of array
size = sizeof(arr2) / sizeof(arr2);
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);
find_fixed_point(arr3, size);
return 0;
}``````

#### Output

`````` 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);
}
}``````

#### Output

`````` 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);
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);
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);
obj.find_fixed_point(arr3, size);
return 0;
}``````

#### Output

`````` 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);
}
}``````

#### Output

`````` 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();``````

#### Output

`````` 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();``````

#### Output

`````` 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()``````

#### Output

`````` 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()``````

#### Output

`````` 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);
}
}``````

#### Output

`````` 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();``````

#### Output

`````` 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.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post