Repeating Elements

How to find the repeating elements in arrays using C++ STL???

1 Like

Sort the array using STL and then traverse the array linearly. Now, all duplicates will be side by sode. Now you can easily find the similar elements

1 Like

Find the two repeating elements in a given array
You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.

For example, array = {4, 2, 4, 5, 2, 3, 1} and n = 5

The above array has n + 2 = 7 elements with all elements occurring once except 2 and 4 which occur twice. So the output should be 4 2.

We strongly recommend that you click here and practice it, before moving on to the solution.

Method 1 (Basic)
Use two loops. In the outer loop, pick elements one by one and count the number of occurrences of the picked element in the inner loop.

This method doesn’t use the other useful data provided in questions like range of numbers is between 1 to n and there are only two repeating elements.

Method 2 (Use Count array)
Traverse the array once. While traversing, keep track of count of all elements in the array using a temp array count[] of size n, when you see an element whose count is already set, print it as duplicate.

This method uses the range given in the question to restrict the size of count[], but doesn’t use the data that there are only two repeating elements.

Time Complexity: O(n)
Auxiliary Space: O(n)
Method 3 (Make two equations)

Let the numbers which are being repeated are X and Y. We make two equations for X and Y and the simple task left is to solve the two equations.
We know the sum of integers from 1 to n is n(n+1)/2 and product is n!. We calculate the sum of input array, when this sum is subtracted from n(n+1)/2, we get X + Y because X and Y are the two numbers missing from set [1…n]. Similarly calculate product of input array, when this product is divided from n!, we get X*Y. Given sum and product of X and Y, we can find easily out X and Y.

Let summation of all numbers in array be S and product be P

X + Y = S – n(n+1)/2
XY = P/n!

Using above two equations, we can find out X and Y. For array = 4 2 4 5 2 3 1, we get S = 21 and P as 960.

X + Y = 21 – 15 = 6

XY = 960/5! = 8

X – Y = sqrt((X+Y)^2 – 4*XY) = sqrt(4) = 2

Using below two equations, we easily get X = (6 + 2)/2 and Y = (6-2)/2
X + Y = 6
X – Y = 2

Time Complexity: O(n)
Auxiliary Space: O(1)

Method 4 (Use XOR)
Thanks to neophyte for suggesting this method.
The approach used here is similar to method 2 of this post.
Let the repeating numbers be X and Y, if we xor all the elements in the array and all integers from 1 to n, then the result is X xor Y.
The 1’s in binary representation of X xor Y is corresponding to the different bits between X and Y. Suppose that the kth bit of X xor Y is 1, we can xor all the elements in the array and all integers from 1 to n, whose kth bits are 1. The result will be one of X and Y.

Method 5 (Use array elements as index)

Thanks to Manish K. Aasawat for suggesting this method.

Traverse the array. Do following for every index i of A[].
{
check for sign of A[abs(A[i])] ;
if positive then
make it negative by A[abs(A[i])]=-A[abs(A[i])];
else // i.e., A[abs(A[i])] is negative
this element (ith element of list) is a repetition
}
Example: A[] = {1, 1, 2, 3, 2}
i=0;
Check sign of A[abs(A[0])] which is A[1]. A[1] is positive, so make it negative.
Array now becomes {1, -1, 2, 3, 2}

i=1;
Check sign of A[abs(A[1])] which is A[1]. A[1] is negative, so A[1] is a repetition.

i=2;
Check sign of A[abs(A[2])] which is A[2]. A[2] is positive, so make it negative. ’
Array now becomes {1, -1, -2, 3, 2}

i=3;
Check sign of A[abs(A[3])] which is A[3]. A[3] is positive, so make it negative.
Array now becomes {1, -1, -2, -3, 2}

i=4;
Check sign of A[abs(A[4])] which is A[2]. A[2] is negative, so A[4] is a repetition.
Note that this method modifies the original array and may not be a recommended method if we are not allowed to modify the array.

1 Like

I think the second method is unsuitable. This is because if the array elements have a large value, say 10^9 ( considering int array for simlicity) then you cannot use count arrays. Although for smaller limits, it is OK.

Ok so I will try a hardcore and unique STL solution

set < int > s;

vector<int> v={2,3,4,6,4,8,12,6,9,7,3,2,11,2,56,7,3,88,8};

sort(v.begin(),v.end());

vector<int>::iterator it=adjacent_find(v.begin(),v.end());

while(it!=v.end())
    {

s.insert(*it);

it=adjacent_find(++it,v.end());

}

for(auto &x:s)

cout << x << endl;

Sorting the array brings all repeating elements adjacent and then I use adjacent_find function to find repeating adjacent elements and I store it in set so that even if a number is repeated multiple times, I only encounter it once and then I use auto to iterate over set so overall I have tried to use STL as much as possible.

Hope it helps

1 Like

See my code below which is more simpler and easy to implement than above discussed method.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    unordered_map<int,int>mp;
    int n=8;
    int arr[]={4,2,6,4,2,5,6,2};
    for(int i=0;i<n;++i)
    {
        mp[arr[i]]++;
    }
    for(auto &ele:mp)
    {
    cout<<"Repeated elements of "<<ele.first <<" = "<<ele.second<<endl;
    }


    return 0;
}

Click here

I used hashing concept only.

Time Complexity: O(N)

1 Like

But in your code you show the Occurence of elements…
Please show the repeating elements…

@rashedcs See this code again. I change a little bit. I hope this one is better than any other method

what if we put the elements of the user’s array into a set , which removes duplicat elements !

1 Like

To print the duplicate elements in sorted order, use

**`map`**

Complexity:O(nlogn)

See this code for implementation

To print the duplicate elements in the order they appear in array, use

**`unordered_map`**

Complexity:O(n)

See this code for implementation

2 Likes