print first repeating element using hashmap;

Question

#include <bits/stdc++.h>
using namespace std;

int main() {
    unordered_map<int,int>h;
    int T;
    int n,i;
    cin>>T;
    while(T--)
    {  int flag=0;
        cin>>n;
        int arr[n];
        for( i=0;i<n;i++)
        {
            cin>>arr[i];
        }
        for(i=0;i<n;i++)
        {
            h[i]=count(arr,arr+n,arr[i]);
        }
        for(auto x: h)
        {
            if(x.second>1)
            { flag=1;
                cout<<x.first<<endl;
                break;
            }

        }
           if(flag==0)
           {  cout<<-1<<endl;
           }
    }

}

Given an integer array. The task is to find the first repeating element in the array i.e., an element that occurs more than once and whose index of first occurrence is smallest.

I am getting infinite result. what am I don't wrong. the test cases are below

Input:

test case :1 
array size:7 
array(1 5 3 4 2 4 5 )

Output:

This can be done by using a `std::unordered_set`, and a lot less code than you have now. — PaulMcKenzie, Jun 14 '20 at 18:50
**Recommended reading:** [Why should I not #include ?](https://stackoverflow.com/q/31816095/560648) — Asteroids With Wings, Jun 14 '20 at 18:56
@AsteroidsWithWings This must probably be some question from a contest and in such cases, there's no down-side to using `bits/stdc++.h`. Not including it isn't applicable in every case — Abhishek Bhagate, Jun 14 '20 at 18:57
For those willing to help that use a conforming compiler such as Visual C++, that `bits` header becomes something that has to be removed. — PaulMcKenzie, Jun 14 '20 at 18:59
@AsteroidsWithWings `bits/stdc++.h` exists for a reason. Granted that using it in each places is a bad practice. But in some scenarios, using it does make sense. Competitive coding is just an example for it — Abhishek Bhagate, Jun 14 '20 at 19:04
@Abhishek Yes, it does exist for a reason. You using it is not, and has never been, that reason. — Asteroids With Wings, Jun 14 '20 at 19:04
@AsteroidsWithWings So even you agree that its okay to use `bits/stdc++.h` in competitive programming. Glad that we agree :) — Abhishek Bhagate, Jun 14 '20 at 19:06
There is no competition here on Stack Overflow. Not only is that `bits` header an annoyance for anyone using a well-established compiler like Visual C++, you have the non-standard VLA syntax that gets in the way. Then you have the `while (--t)` "test case" loop, instead of the poster placing the test case data directly in the code. All of this is a time-waster for persons who really want to help. In addition, why is there no "competitive debugging" being done by posters? It seems that we get the question, and we're asked to debug the code. — PaulMcKenzie, Jun 14 '20 at 19:09
@AsteroidsWithWings *crock*, *fake programming*, *plague*. Ok, not shaming :) — Abhishek Bhagate, Jun 14 '20 at 19:10
@PaulMcKenzie I agree. Nobody's saying that we should use bits header in our projects/program applications. As I did say, I do agree that its a bad practice using it everywhere as a hack. But that doesn't mean it should never be used in anyplace whatsoever. Almost everyone uses bits header in Competitive coding and that probably helps in that case. OP probably just copied his code from some contest question that he was attempting. Nothing bad in using bits header in that case. — Abhishek Bhagate, Jun 14 '20 at 19:14

score 1 · Accepted Answer · answered Jun 14 '20 at 19:52

Since you're using an std::unordered_map, the approach should be very simple:

Set the minimum position to a large value.

Loop on the number data from first item to last.
    If the number does not exist in the map, then 
       Add the item and position to the map
    else
       Set the minimum position to min(minimum position, position found in map)

There is no need for flag variables (which will almost always cause issues somewhere, and most likely the reason for your error), or a recount over and over again of the items in the original array like this:

for(i=0;i<n;i++)
{
    h[i]=count(arr,arr+n,arr[i]);
}

If you had 1000 numbers, you would be calling this count loop 1000 times. That is very inefficient.

As to your implementation, where do you store the index of the first duplicate? I don't see it, unless it is hidden behind all of the manipulations you're doing with this flag variable. Whatever you're doing, it is wrong.

Here is an implementation, using your test data and using the outline I presented earlier:

#include <unordered_map>
#include <iostream>
#include <algorithm>
#include <climits>

int main() 
{
    std::unordered_map<int, int> numbers;
    int test[] = {1, 5, 3, 4, 2, 4, 5}; 

    // Set minimum index to a large value
    int minIndex = std::numeric_limits<int>::max();

    for (size_t i = 0; i < std::size(test); ++i )
    {
        // check if item is found
        auto iter = numbers.find(test[i]);
        if ( iter == numbers.end())
           // not found, so add item and position 
           numbers.insert({test[i], i});
        else
           // set the minimum index to the found position and exit the loop
           minIndex = std::min(minIndex, iter->second);
    }
    if ( minIndex == std::numeric_limits<int>::max()) 
        std::cout << -1;
    else
        std::cout << minIndex;
}

Output:

This is effectively has O(n) runtime, as opposed to what you wrote, which was O(n^2) due to the inefficient counting loop.

score 0 · Answer 2 · answered Jun 14 '20 at 19:03

despite the question, this line of code

int arr[n];

is not allowed in C++ even if your local IDE didn't give any errors I think your online judge will give a runtime error.

As the arrays in C++ must be statically allocated which means you need to know the number of elements of the array before you run the code.

print first repeating element using hashmap;

2 Answers2