# Find the first Repeating Number in a Given Array  Difficulty Level Easy
Array Hash Searching Zynga

## Problem Statement  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.

### Implementation

#### Java Program

```import java.util.HashMap;
import java.util.Scanner;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
HashMap <Integer,Integer> m = new HashMap<Integer, Integer>();
int ans=0;
for(int i=0;i<n;i++)
{
int x = m.get(a[i])==null ? 1: m.get(a[i])+1;
m.put(a[i], x);
if(m.get(a[i])>1)
{
ans=a[i];
break;
}
}
if(ans==0)
{
System.out.println("No element repeated");
}
else
{
System.out.println(ans);
}
}
}```
```12
5 4 2 8 9 7 12 5 6 12 4 7```
`5`

### 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.

Find minimum number of merge operations to make an array palindrome

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

### Implementation

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

}```

#### Java Program

```import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
Map <Integer,Integer> m = new HashMap<Integer, Integer>() {}; // create a map with key as the array element and value as if it is present or not
int frank=0;
for(int i=0;i<n;i++)
{
boolean temp = m.containsValue(a[i]);
if(temp) // if present then it is the first element to be repeated
{
System.out.println(a[i]);
frank=1;
i=n;
}
else
{
m.put(a[i],1); //else insert it into the map setting the value as true
}
}
if(frank==0)
System.out.println("No element repeated");
}
}```
```6
1 2 3 4 5 6```
`No element repeated`