How to Find the Elements Equal to Their Index

In this problem, we are given an array of positive integers, and we need to find the elements whose value is equal to their index (1-based indexing).

Let’s understand the problem with an example:

Example:

Input: N = 5 Arr[ ] = {15, 2, 45, 12, 7}

Output: 2

Explanation: Only Arr[2] = 2 exists here.

Approach:

To solve this problem efficiently, we can iterate through the given array and check each element. If the value of the element is equal to its index (considering 1-based indexing), we include its index in the result.

Here’s a step-by-step approach:

1. Initialize an empty array to store the indices of elements satisfying the condition.
2. Iterate through the given array and check each element:
   • If the value of the element is equal to its index (index + 1 due to 1-based indexing), include its index in the result array.
3. Finally, return the result array.

Pseudocode:

function valueEqualToIndex(arr[], n):
result = empty array

for i from 1 to n:
if arr[i] == i + 1:
add i to result

return result


Implementation:

python code
def valueEqualToIndex(arr, n):
    result = []
    for i in range(n):
        if arr[i] == i + 1:
            result.append(i + 1)
    return result

Complexity Analysis:

• Time Complexity: O(N), where N is the number of elements in the array. We iterate through the array once.
• Space Complexity: O(k), where k is the number of elements satisfying the condition arr[i] = i + 1. We store these indices in the result array.

Conclusion:

In this tutorial, we learned how to find elements in an array whose value is equal to their index. We followed a simple approach that has a time complexity of O(N), where N is the size of the array. This problem can be efficiently solved using the provided approach.