Skip to content
Count Duplicates of Array O(N)

Count the Duplicates of Array O(N)

In the given problem, we have a sorted array, and we need to count the duplicates of each element. In simple words, we should print the no.of times each element occurs.

Example

Input: [1,2,2,4,5,5,5,6]
Output:
2 appears 2 times
5 appears 3 times

Solution approach

Since we have a sorted array, things become much easier. Once we traverse through an element, if it has a duplicate then definitely the next element will be the same, and so on until we traverse through the last duplicate element of the same.

IF a[i] == a[i+1] THEN Duplicates++

With this method we can find

  • No of repeating elements
  • Duplicates of each element and their count

Code to find Duplicates in an Array

#include<iostream>
using namespace std;
int main()
{
    int a[11]={1,4,6,6,8,11,11,15,15,15,16};
    int j=0;
    for(int i=0;i<11-1;i++)
    {
        if(a[i]==a[i+1])
        {
            j=i+1;
            //j contains second duplicate element
            while(a[j]==a[i])j++;
            cout<<a[i]<<" appears "<<j-i<<" times "<<endl;
            //skip all j's we covered.
            i=j-1;
        }
    }
}

Output

6 appears 2 times
11 appears 2 times
15 appears 3 times

Similar problems

Conclusion

I hope you found this helpful, always remember that whenever we\’ve got a sorted array, in most cases we can carry out any kind of operation in a single iteration with O(N) Time Complexity. This post is a part of my #30DaysChallenge to write a blog post every day on what I learn, Cheers~ Abhiram Reddy.

Tags: