Smallest Index with Equal Value

Approach

Iterate through the array and check for each element one by one.

If ‘i’ % 10 == ARR[I], then we found the element. We return the index of the element.

Otherwise, if the condition is not met for any element, then we return -1

Program

#include <vector>
#include <iostream>
using namespace std;
 
int smallestEqual(vector<int> &arr)
{
    // Iterating through the array, 'ARR'.
    for (int i = 0; i < arr.size(); i++)
    {
        // Checking the condition.
        if (i % 10 == arr[i])
            return i;
    }
 
    // If no such index is found, we return -1.
    return -1;
}
 
int main()
{
    // Taking user input.
    int n;
    cin >> n;
    vector<int> arr(n);
 
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
 
    // Calling 'smallestEqual()' function.
    cout << smallestEqual(arr);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

4 
6 2 7 3

Output

3

Time Complexity

O(N), where ‘N’ is the size of the array.

In the worst case, we would traverse the entire array but not find an element that satisfies the condition. Thus it would take O(N) time to traverse the array.

Space Complexity

O(1)

We are just iterating over the array once. Thus we only require a handful of variables. Therefore it will take constant space.

Key takeaways

In this blog, we solved a relatively simple problem, namely Smallest Index with equal value. We solved it using one pass over the array. Thus the time complexity is O(N), and space complexity is O(1). Stay tuned for learning more such exciting problems.

Recommended Readings:

• Binary Search
• Dynamic Programming
• Book Allocation Problem
• Plates Between Candles
• Find the subarray with t
   

Thanks and Happy Coding!!