Find elements having at least K times the minimum frequency
Given an array A, the task is to find elements with the occurrence at least K times the frequency of the least occurring element in the array.
Examples:
Input: A = {4, 4, 3, 6, 6, 6, 8, 9}, K = 2
Output: {4, 6}
Explanation: Frequency Table : {4:2, 3:1, 6:3, 8:1, 9:1},
least occurring elements in nums are 8 and 9 with occurrence of 1.
The elements required with 2 times of minimum occurrence i.e. 2
are 4 and 6. As 4 is occurring 2 times and 6 is occurring 3 times.Input: A = {3, 3}, K = 4
Output: {}
Approach: The idea is as mentioned below:
Store the frequency of each element and find the minimum frequency and then for each frequency check whether (K * min frequency) is less than or equal to the current frequency.
Follow the below steps to solve the problem:
- Store all the elements of the array in a map/hash table with their frequency
- Iterate over the elements of the map and find the minimum frequency.
- Now, find the elements which occur more than K times this minimum occurrence.
Below is the implementation of this approach:
C++
// C++ code to implement this approach #include <bits/stdc++.h> using namespace std; void nums_with_least_occurrence(vector< int > A, int K) { // create an unordered map for storing the occurrences of // elements of array unordered_map< int , int > ump; // iterate over nums array and store occurrences in map for ( int i : A) ump[i]++; // find minimum occurrence in map int mini_occurrence = INT_MAX; for ( auto m : ump) { if (m.second < mini_occurrence) mini_occurrence = m.second; } // create an vector to store elements occurring greater than 2 // times than least occurrence vector< int > ans; // iterate through map and check for elements whose // occurrence is greater than equal 2 times than least // occurrence for ( auto m : ump) { if (m.second >= (K * mini_occurrence)) { ans.push_back(m.first); } } if (ans.size() == 0) cout << "No elements found" ; else { for ( int i : ans) cout << i << " " ; } cout << endl; } // Driver Code int main() { vector< int > A{ 4, 4, 3, 6, 6, 6, 8, 9 }; int K = 2; nums_with_least_occurrence(A, K); return 0; } |
Java
// Java code to implement this approach import java.util.*; class GFG { public static void nums_with_least_occurrence( int A[], int K) { // create an unordered map for storing the // occurrences of elements of array Map<Integer, Integer> hashmp = new HashMap<Integer, Integer>(); // iterate over nums array and store occurrences in // map for ( int i = 0 ; i < A.length; i++) { if (hashmp.containsKey(A[i])) { hashmp.put(A[i], hashmp.get(A[i]) + 1 ); } else { hashmp.put(A[i], 1 ); } } // find minimum occurrence in map int mini_occurrence = Integer.MAX_VALUE; for (Map.Entry<Integer, Integer> entry : hashmp.entrySet()) { if (entry.getValue() < mini_occurrence) mini_occurrence = entry.getValue(); } // create an array to store elements greater than 2 // times than least occurrence ArrayList<Integer> ans = new ArrayList<Integer>(); // iterate through map and check for elements whose // occurrence is greater than equal 2 times than // least occurrence for (Map.Entry<Integer, Integer> entry : hashmp.entrySet()) { if (entry.getValue() >= K * mini_occurrence) ans.add(entry.getKey()); } if (ans.isEmpty()) System.out.println( "No elements found" ); else { for ( int i = 0 ; i < ans.size(); i++) System.out.print(ans.get(i) + " " ); } System.out.println(); } // Driver Code public static void main(String[] args) { int [] A = { 4 , 4 , 3 , 6 , 6 , 6 , 8 , 9 }; int K = 2 ; nums_with_least_occurrence(A, K); } } |
Python3
# Python code to implement this approach import math def nums_with_least_occurrence(A, K): # create an unordered map for storing the occurrences of # elements of array mp = {} # iterate over nums array and store occurrences in map for i in A: if i not in mp: mp[i] = 1 else : mp[i] + = 1 # find minimum occurrence in map mini_occurrence = math.inf for v in mp.values(): if v < mini_occurrrence: mini_occurrence = v # create an vector to store elements greater than 2 # times than least occurrence ans = [] # iterate through map and check for elements whose # occurrence is greater than equal 2 times than least # occurrence for k, v in mp.items(): # print(v, 2 * mini_occurrence) if v > = K * mini_occurrence: ans.append(k) if len (ans) = = 0 : print ( "No elements found" ) else : for i in ans: print (i, end = " " ) # Driver Code if __name__ = = "__main__" : A = [ 4 , 4 , 3 , 6 , 6 , 6 , 8 , 9 ] K = 2 nums_with_least_occurrence(A, 2 ) |
C#
// C# code to implement this approach using System; using System.Collections; using System.Collections.Generic; public class GFG { static void nums_with_least_occurrence( int [] A, int K) { Dictionary< int , int > hashmp = new Dictionary< int , int >(); for ( int i = 0; i < A.Length; i++) { if (hashmp.ContainsKey(A[i])) { hashmp[A[i]] += 1; } else { hashmp.Add(A[i], 1); } } int mini_occurence = Int32.MaxValue; foreach (KeyValuePair< int , int > entry in hashmp) { if (entry.Value < mini_occurence) { mini_occurence = entry.Value; } } var ans = new ArrayList(); foreach (KeyValuePair< int , int > entry in hashmp) { if (entry.Value >= K * mini_occurence) { ans.Add(entry.Key); } } if (ans.Count == 0) { Console.WriteLine( "No elements found" ); } else { foreach ( var i in ans) { Console.Write(i + " " ); } } Console.WriteLine(); } static public void Main() { // Code int [] A = { 4, 4, 3, 6, 6, 6, 8, 9 }; int K = 2; nums_with_least_occurrence(A, K); } } /* Note : The output you may see when you run the code will * be 4, 6 because in the input array 4 comes before 6 * and hence the dictionary will store them in order only. */ // This code is contributed by lokeshmvs21. |
Javascript
// JavaScript code to implement this approach function nums_with_least_occurrence( A, K) { // create an unordered map for storing the occurrences of // elements of array let ump ={}; // iterate over nums array and store occurrences in map for (let i of A) { if (ump.hasOwnProperty(i)) ump[i]++; else ump[i]=1; } // find minimum occurrence in map let mini_occurrence = 1e9+7; for (let key in ump) { if (ump[key] < mini_occurrence) mini_occurrence = ump[key]; } // create an vector to store elements occurring greater than 2 // times than least occurrence let ans = []; // iterate through map and check for elements whose // occurrence is greater than equal 2 times than least // occurrence for (let key in ump) { if (ump[key] >= (K * mini_occurrence)) { ans.push(key); } } if (ans.length === 0) console.log( "No elements found" ); else { console.log(ans); } } // Driver Code let A = [ 4, 4, 3, 6, 6, 6, 8, 9 ]; let K = 2; nums_with_least_occurrence(A, K); // This code is contributed by Ishankhandelwals. |
6 4
Time complexity: O(N)
Auxiliary Space: O(N)