Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Problem Statement
2.1.
Input
2.2.
Output
3.
Approach
4.
Program
4.1.
Input
4.2.
Output
4.3.
Time Complexity
4.4.
Space Complexity
5.
Key takeaways
Last Updated: Mar 27, 2024

Smallest Index with Equal Value

Author Husen Kagdi
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction 

The key to success in competitive programming is solving up a lot of easy problems and medium problems, and quite a handful of hard problems. First, you should solve a lot of Easy problems to get command over language and its tools. It would improve your implementation skills. So let us discuss an easy problem today from Leetcode. Have a look at the problem statement below.

Also see,  Rabin Karp Algorithm

Problem Statement

Given an 0-index array, ‘ARR’, return the smallest index that satisfies the following condition:

    ‘i’ % 10 = ARR[i], where i is the index of the array.

If no such element exists, then return -1.

Recall that X % Y is the remainder when X is divided by Y.

Input

4

6 2 7 3

Output

3

Here ARR[2] = 2. Now 2 % 10 = 2 and ARR[2] is also equal to 2. Therefore the answer is 2 here. There is no other smallest index that satisfies the condition mentioned in the problem.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

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:

Thanks and Happy Coding!!

Previous article
Alternative Sorting
Next article
Find The Last
Live masterclass