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:
-
Array:
[8, 3, 1, 6, 4]
- Here, the fixed point is
4
sincearr[4]
is equal to4
.
- Here, the fixed point is
-
Array:
[4, 2, 7, 9, 2, 9, 1]
- There is no fixed point in this array.
-
Array:
[4, 1, 7, 9, 2, 5, 1]
- Here, the fixed point is
1
sincearr[1]
is equal to1
.
- Here, the fixed point is
Idea to Solve the Problem
To solve this problem, we can follow these steps:
- Iterate through the array and compare each element with its index.
- If an element is equal to its index, that index is a fixed point.
- 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
- Initialize
location
to-1
. - Iterate through the array using a loop that goes from
0
tosize-1
. - For each index
i
, check if the elementarr[i]
is equal toi
. - If the condition is met, set
location
toi
and break the loop. - Display the array elements.
- If
location
is still-1
, it means no fixed point was found. Display "Fixed point not exists." - If
location
is not-1
, display "Fixed point is" followed by the value oflocation
.
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[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;
}
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[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;
}
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.
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.
New Comment