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.