We are going to find the ** First Repeating Element In An Array** but before this, I hope you know what the array,

**is. I am not going to make this post long so let’s start.**

*binary search, set**Example*

```
Input Array - [1, 2, 3, 4, 3, 5];
First repeated element is 3
```

Table of Contents

*Algorithm to find first repeating element in an array*

*Algorithm to find first repeating element in an array*

*Using Sorting O(n log(N))**A*nother Efficient wayO(n)*Hashing**Using Two Nested Loop O(N^2)*

Here we are discussing the all the three ways with the code to find f**irst repeating element in an array.**

*Using Sorting*

*Using Sorting*

I assume you know about sorting techniques like the bubble sort, merge sort, etc, and also C++ STL function ** sort**.

#### Algorithm:

- We first copy the given array to another array named as aux[]
- Sort the elements of aux[]
- Scan the given array from left to right and check each element occurrence in aux[] and the first element that repeats twice is our answer

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

/* if x is present in arr[] then returns the index of FIRST occurrence of x in arr[0..n-1], otherwise returns -1 */int first(int arr[], int low, int high, int x, int n) { if(high >= low) { int mid = (low + high)/2; /*low + (high - low)/2;*/ if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x) return mid; else if(x > arr[mid]) return first(arr, (mid + 1), high, x, n); else return first(arr, low, (mid -1), x, n); } return -1; }/* if x is present in arr[] then returns the index of LAST occurrence of x in arr[0..n-1], otherwise returns -1 */int last(int arr[], int low, int high, int x, int n) { if (high >= low) { int mid = (low + high)/2; /*low + (high - low)/2;*/ if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x ) return mid; else if(x < arr[mid]) return last(arr, low, (mid -1), x, n); else return last(arr, (mid + 1), high, x, n); } return -1; }/* if x is present in arr[] then returns the count of occurrences of x, otherwise returns -1. */int count(int arr[], int x, int n) { int i; // index of first occurrence of x in arr[0..n-1] int j; // index of last occurrence of x in arr[0..n-1]/* get the index of first occurrence of x */i = first(arr, 0, n-1, x, n);/* If x doesn't exist in arr[] then return -1 */if(i == -1) return i;/* Else get the index of last occurrence of x. Note that we are only looking in the subarray after first occurrence */j = last(arr, i, n-1, x, n); /* return count */ return j-i+1; } int main() { int n; cin>>n; int arr[n]; for(int i = 0;i<n;i++) cin>>arr[i]; int aux[n]; for(int i = 0;i<n;i++) aux[i] = arr[i]; sort(aux,aux+n); // Sorting the aux[] int check = 0; for(int i = 0;i<n;i++) { if(count(aux,arr[i],n)>1) { cout<<"Repeated Element is "<<arr[i]; check = 1; break; } } if(check == 0) cout<<"No element Repeated"<<endl; return 0; }

Input array = [2, 1, 4, 3, 2]

After sorting and adding to aux[] = [1, 2, 2, 3, 4]

Now traversing array from left to right and checking in aux using binary search and we get 2 as our answer.

### Hashing:

I assume you know about Set in C++. What I am going to do is

#### Algorithm

- Add element of array in Set from right
- check from the right hand side and if element is present we add to min variable
- If element is not present we add it to the set

```
#include <bits/stdc++.h>
using namespace std;
int count(int aux[], int n)
{
int min = -1; //Initialize with -1
set<int> s; // Creating set
for(int i = n-1;i>=0;i--)
{
if (s.find(aux[i]) != s.end()) // finding element to set.
min = i;
else
s.insert(aux[i]); // adding element to set.
}
return min;
}
int main() {
int n;
cin>>n;
int arr[n];
for(int i = 0;i<n;i++)
cin>>arr[i];
if(count(arr,n)!=-1)
cout<<"Repeated Element is "<<arr[count(arr,n)];
else
cout<<"No element Repeated"<<endl;
return 0;
}
```

### Using Two Nested Loop:

This is simplest and most time consuming algorithm, The steps are given below

- Make two nested loop
- Outer loop picks up element
- Inner loop counts occuerence in array

```
#include <bits/stdc++.h>
using namespace std;
int count(int aux[], int n)
{
for(int i = 0;i<n;i++)
{
int count = 0;
for(int j = 0;j<n;j++)
{if(aux[j] == aux[i])
{
count++;
}
if(count>1)
return aux[j];
}
}
return -1;
}
int main() {
int n;
cin>>n;
int arr[n];
for(int i = 0;i<n;i++)
cin>>arr[i];
if(count(arr,n)!=-1)
cout<<"Repeated Element is "<<count(arr,n);
else
cout<<"No element Repeated"<<endl;
return 0;
}
```

## Conclusion:

This is all I know about f** inding the **first repeating element in the array. I show the code also if you have any doubts then please comment and in case of any mistake please correct us.