# Find First Repeating Element In An Array

We are going to find the First Repeating Element In An Array but before this, I hope you know what the array, binary search, set is. I am not going to make this post long so let’s start.

Example

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

## Algorithm to find first repeating element in an array

• Using Sorting O(n log(N))
• Another Efficient way Hashing O(n)
• Using Two Nested Loop O(N^2)

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

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