Program to find repeating element in an array (duplicate elements)

Finding the non repeating element in an array can be done in 2 different ways.

Method 1: Use two loops, one for the current element and the other to check if the element is already encountered or not.

Method 2: Traverse the array and insert the array elements and their number of occurances in the hash table. Traverse the array again and print the array elements having count > 1.

Method 3: Traverse the array from start to end and perform arr[i]%n and increment its value by n. Then, traverse the array again and print all those indexes i for which arr[i]/n is greater than 1. 

Method 1 to find repeating element in an array

An easier approach to find all repeating elements in an array is to use two loops. Use the first loop for traversing the array and the second loop to check if the current element is already encountered.

Algorithm

  1. Declare the array and input the array elements.
  2. Start traversing the array and check if the current element is already encountered.
  • If it is already encountered, print the element as a repeating element and continue.
  • If not, move to the next element of the array and continue
#include <stdio.h>
#include <stdlib.h>
using namespace std;
void repeating_element(int arr[], int n)
{
int i;
int count = 0;
for(i = 0;i < n;i++)
{
if (arr[abs(arr[i])] >= 0)
arr[abs(arr[i])] = -arr[abs(arr[i])];
else
{
++count;
printf("\nRepeating element [%d] : %d\n",count,abs(arr[i]));
}
}
printf("\n");
printf("Frequency : %d\n",count);
}
int main()
{
int n;
printf("\nEnter the number of elements : ");
scanf("%d",&n);
int arr[n];
int i;
printf("\nInput the array elements : ");
for(i = 0; i < n; i++)
{
scanf("%d",&arr[i]);
}
repeating_element(arr,n);
return 0;
}
#include <iostream>
#include <stdlib.h>
using namespace std;
int repeating_element(int arr[], int n)
{
int i;
int count = 0;
for(i = 0;i < n;i++)
{
if (arr[abs(arr[i])] >= 0)
arr[abs(arr[i])] = -arr[abs(arr[i])];
else
{
++count;
cout << "\nRepeating element ["<< count << "] : " <<abs(arr[i]) << " ";
cout << endl;
}
}
cout << endl;
cout << "Frequency : " << count << endl;
}
int main()
{
int n;
cout << "\nEnter the number of elements : ";
cin >> n;
int arr[n];
int i;
cout << "\nInput the array elements : ";
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
repeating_element(arr,n);
return 0;
}

Method 2 for finding repeating element in an array

The time complexity of this problem can be reduced by using hash tables. The array is traversed and the array elements along with their counts is stored in the hash table. Then the array is traversed again and the elements having  count > 1 are displayed as repeating elements or duplicate elements in the array.

Algorithm

  • Declare the array and input the array elements.
  • Insert all the array elements in the hash table.
  • Traverse the array again and display the array elements having their count = 1.
#include <iostream>
#include <unordered_map>
using namespace std;
void non_repeating_elements(int arr[], int n)
{
unordered_map<int, int> table;
for (int i = 0; i < n; i++)
table[arr[i]]++;
for (auto e : table)
if (e.second > 1)
cout << e.first << " ";
}
int main()
{
int n,i;
cout << "\nEnter the number of elements : ";
cin >> n;
int arr[n];
cout << "\nInput the array elements : ";
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
non_repeating_elements(arr, n);
return 0;
}
from collections import defaultdict
def repeating_element(arr):
dict = {}
for x in arr:
try:
dict[x] += 1
except:
dict[x] = 1
for data in dict:
if(dict[data] > 1):
print(data, end=" ")
print (" ")

# Main Function

n = int(input("Enter the number of elements : "))
print("Input the array elements : ")
for i in range(0,n):
arr[i] = int(input())
print(repeating_element(arr))

Method 3 to find repeating element in an array

  • Traverse the array from start to end.
  • Perform arr[i]%n and increment its value by n.
  • Then, traverse the array again and print all those indexes i for which arr[i]/n is greater than 1. 
  • arr[i]/n will be greater than 1 only when “i”(the element)  has appeared more than once.

Algorithm

  1. Declare the array and input the array elements.
  2. Start traversing the array and perform arr[i] % n and add with ‘n’ for all value of ‘i’.
  3. Traverse the array again and check arr[i] / n.
  4. If it is greater than 1, print it as a duplicate element and continue.
  5. Else, move to the next element and continue.
#include <stdio.h>
void repeating_elements(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
int index = arr[i] % n;
arr[index] = arr[index] + n;
}
for (int i = 0; i < n; i++)
{
arr[i] = arr[i] / n;
if ((arr[i]) > 1)
printf("%d ",i);
}
}
int main()
{
int n,i;
printf("\nEnter the number of elements : ");
scanf("%d",&n);
int arr[n];
printf("\nInput the array elements : ");
for(i = 0; i < n; i++)
{
scanf("%d",&arr[i]);
}
repeating_elements(arr, n);
return 0;
}
#include <iostream>
using namespace std;
void repeating_elements(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
int index = arr[i] % n;
arr[index] = arr[index] + n;
}
for (int i = 0; i < n; i++)
{
arr[i] = arr[i] / n;
if ((arr[i]) > 1)
cout << i << " ";
}
}
int main()
{
int n,i;
cout << "\nEnter the number of elements : ";
cin >> n;
int arr[n];
cout << "\nInput the array elements : ";
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
repeating_elements(arr, n);
return 0;
}

Test case:

  • Input: 1 2 3 1 2
  • Output: 1 2 

Output:

repeating element in an array