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

By Harsh Gupta

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