Count More than n/k Occurences

Given an array arr[] of size N and an element k. The task is to find all elements in array that appear more than n/k times.

Example 1:

Input:
N = 8
arr[] = {3,1,2,2,1,2,3,3}
k = 4
Output: 2
Explanation: In the given array, 3 and
 2 are the only elements that appears 
more than n/k times.

Example 2:

Input:
N = 4
arr[] = {2,3,3,2}
k = 3
Output: 2
Explanation: In the given array, 3 and 2 
are the only elements that appears more 
than n/k times. So the count of elements 
are 2.



method 1 : hashing:

1)traverse the array and store all the elements in the map along with frequency of each elements

2)now traverse through the map and if freqeuncy of that particular element is greater than n/k , then increment counter (int c in below code).

3) then return counter at the end.



c++ implementation:

int countOccurence(int a[], int n, int k) 
{
       unordered_map<int,int>m; int c=0;
       for(int i=0;i<n;i++)
       m[a[i]]++;
       
       for(auto x:m)
       {
           if(x.second >n/k)
           c++;
       }
       return c;
    }


Time Complexity: O(n) 
space Complexity: O(n) 



darkmode