Home » Technical Interview Questions » Array Interview Questions » Find the first Repeating Number in a Given Array

# Find the first Repeating Number in a Given Array

There can be multiple repeating numbers in an array but you have to find the first repeating number in a given array (occurring the second time).

## Example

Input

12

5 4 2 8 9 7 12 5 6 12 4 7

Output

5 is the first repeating element

## Approach 1 for Find the first Repeating Number

Simply we can Use Hashing where we hash the values of the elements of the array and incrementing the count of occurrence. As soon as we get an element with count 1 i.e. which has occurred already we get the first repeating element.

### Algorithm

1. Traverse each element of the array.

2. Increase the frequency of each element.

3. If any element whose frequency greater than 1 then print that number directly.

### Complexity Analysis for Find the first Repeating Number

Time Complexity– O(N) where N is the size of the array. Here we iterating over the array and store the frequency/count of the elements in hash map.

Space Complexity – O(N) because we count the frequency o element and maximum size possible of hash map is O(n).

## Approaches 2 for Find the first Repeating Number

Here we use map which stores that element present in the array or not. If the element is present then it contains true with respect to that element in the map. If the element is not present then it maintains false with respect to that element in the map.

### Algorithm

1. Use Map by making the value of the array element as the key and count as the key-value pair.

2. Initialize a pair with count as 1 and increment it.

3. As soon as we get an element whose count is 1 we get the first repeating element

### C++ Program

```#include <bits/stdc++.h>
using namespace std;
int main()
{

int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
map <int,bool> M; // create a map with key as the array element and value as if it is present or not
map <int,bool> :: iterator it;
for(int i=0;i<n;i++)
{
it = M.find(arr[i]); //find the array element in map
if(it != M.end()) // if present then it is the first element to be repeated
{
cout<<arr[i] <<endl;
return 0;
}
else
M.insert(make_pair(arr[i],true)); //else insert it into the map setting the value as true
}
cout<<"No element repeated"<<endl;
return 0;

}```
```12
5 4 2 8 9 7 12 -5 6 1 -4 -7```
`No element repeated`

### Complexity Analysis for Find the first Repeating Number

Time Complexity – O(NlogN) because insertion in map take O(logn) time and here we insert n elements int the map.

Space Complexity – O(N) because we use a map which stores that element is present on not.

References

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions