Elements Appear more than N/K times in Array

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg Facebook Google Microsoft Zenefits
Array Binary Search Hash Hashing HashMapViews 2781

Problem Statement

In the “Elements Appear more than N/K times in Array” problem we have given an integer array of size n. Find the elements which appear more than n/k times. Where k is the input value.

Input Format

The first and only one line containing two integers N and K.

Second-line containing N space-separated integers.

Output Format

The first and only one line containing all those integers with space-separated which are present in the array more than n/k times.

Constraints

  • 1<=N,K<=10^5
  • -10^9<=a[i]<=10^9

Example

7 6
1 3 4 7 4 7 5
4 7

Explanation: Size of the array (n) = 7, n/k = 1.  Therefore, we need to find elements that are coming more than 1 time.
Therefore, output: [4, 7].

10 5
1 1 1 2 2 3 3 4 4 5
1

Explanation: Size of the array (n) =10, n/k = 2. Therefore, we need to find elements that are coming more than 2 times.
Therefore, output: [1].

Algorithm

  1. Traverse the whole array element by element.
  2. If the current element is not present in the map then add it to the map with the value 1.
  3. Else find the current freq of this element and add it into the map with the value freq+1.
  4. Traverse the whole map and check the value of each key. If the key is greater than n/k then print the key.
  5. Otherwise, move to the next element.

Implementation

C++ Program for Elements Appear more than N/K times in Array

#include <bits/stdc++.h>
using namespace std;

int main()
{
   int n,k;
   cin>>n>>k;
   int a[n];
   for(int i=0;i<n;i++)
   {
       cin>>a[i];
   }
   int req = n/k;
   unordered_map<int,int> m;
   for(int i=0;i<n;i++)
   {
       m[a[i]]++;
   }
   for(auto u: m)
   {
       if(u.second>req)
       {
           cout<<u.first<<" ";
       }
   }
   cout<<endl;
   return 0;
}

Java Program for Elements Appear more than N/K times in Array

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int k = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
        for(int i=0;i<n;i++)
        {
            int val = m.get(a[i])== null? 0 : m.get(a[i]);
            m.put(a[i], val+1);
        }
        for(Map.Entry u : m.entrySet())
        {
            int val = (int) u.getValue();
            if(val > (n/k))
            {
                System.out.print(u.getKey()+" ");  
            }     
        }
        System.out.println();
        }
}
7 3
3 4 3 4 3 4 1
3 4

Complexity Analysis for Elements Appear more than N/K times in Array

Time Complexity

O(n) where n is the size of the given array a[]. Here we traverse the whole array and find the freq of each element and store it in a hashmap.

Space Complexity

O(n) where n is the size of the given array a[]. Here we use the map to store the frequency of each element.

Translate »