Find Numbers with prime frequencies greater than or equal to k in C ++

We are given an array of positive integers and our task is to find the numbers which appear prime number of times and whose frequency is greater than or equal to a given number ‘k’.

Understand with example:

Let’s understand what we are going to do with example

Input: arr[] = {2,1,4,5,12,56,2,3,2,56,56,56,1,56,1} , k = 3

Output: 2 , 1 , 56

2 and 1 occur three times and 56 occurs five times.

Input: arr[] = {2,1,4,5,12,56,2,3,2,56,56,56,1,56,1} , k = 7

Output: -1     i.e no element occurs prime no. of times and frequency greater than or equal to 7.

Approach:

• We will create a hash map and store numbers present in the array as key and their count as values in the map.
• Now we will traverse the map and check if the count of a particular key is prime and greater than or equal to ‘k’. If yes, then we will print that key.

Below is our C++ code to find numbers with prime frequencies greater than or equal to k:

#include<iostream>
#include<unordered_map>
using namespace std;

bool isPrime(int f) 
{ 
     
    if (f <= 1) 
        return false; 
  
    // Check if f is divisible by any number from 2 to f-1 
    for (int j = 2; j < f; j++) 
        if (f % j == 0) 
            return false; 
  
    return true; 
} 

// Function to print numbers with prime frequency and frequency 
// greater than or equal to k  
void frequencyPrime(int ar[], int k, int size) 
{ 
    unordered_map<int, int> freqMap; 
      
    // Insert keys and 
    // their counts 
    for (int j = 0; j < size; j++)  
        freqMap[ar[j]]++; 
  
    // Traverse freqMap and print element with prime frequency 
    // and frequency 
    // greater than or equal to k  
    for (auto element : freqMap)  
    { 
        if (isPrime(element.second) &&  element.second >= k) 
            cout << element.first << endl; 
    } 
} 

int main() 
{ 
    int ar[] = {2,1,4,5,12,56,2,3,2,56,56,56,1,56,1}; 
    int k = 3; 
    int n = sizeof(ar)/sizeof(ar[0]);
  
    frequencyPrime(ar, k, n); 
    return 0; 
}

Output:

Now it’s time to run the code.

After we run the code, we can see the output given below:

2

56

1