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
We hope you have got the solution.
Leave a Reply