Finding numbers with prime frequencies greater than or equal to k is the problem in which we try to find all those numbers that appear a prime number of times and whose frequencies should be greater than or equal to a given number k from an array.

Example

Let's understand the current scenario with an example.

We have given an array of numbers named array1[] and a number k.

In the above-given array, frequencies of 5 is 3, 7 is 5, and 11 is 3 are prime numbers and greater than or equal to k. That's why output should be:

5, 7, 11

Algorithm

This is the approach through which we will find out the expected result.

Declare a map.

Store array data in the map along with their frequencies.

Traverse the map:

For each element check if frequency >= k.

Check If the frequency is a prime number or not.

If the frequency is a prime number then print the key value.

Repeat steps a., b., and c. for each number on the map.

Step 1:

Firstly, We declare a Hashmap. Numbers - Frequencies.

Step 2:

Now we will store the array's data in the map with their frequencies.

Step 3:

Now we iterate the map and check whether the frequency of a given number >=k and frequency== prime number.

After starting iteration from the top, If we find any number whose frequency>=k and frequency==prime number, then we print that number.

The first number that fulfills the condition of the loop is 5. So the program will print 5.

Step 4

In the same manner as step 3, the loop will iterate the whole map and print all the numbers with frequency>=k and frequency==prime.

So That's How we reach our supposed goal.

Note: 1 should not be considered a prime number.

Code in C++ 💻

C++ program to find numbers with prime frequencies greater than or equal to k

#include <bits/stdc++.h>
using namespace std;
/* Check if the number of occurrences are primes or not */
bool PrimeOrNot(int l)
{
/* Corner case */
if (l <= 1) return false;
/* Check from 2 to n-1 */
for (int x = 2; x < l; x++)
if (l % x == 0)
return false;
return true;
}
/* Function to find numbers with prime frequencies greater than or equal to k. */
void PrimeFrequency(int array1[], int k)
{
unordered_map<int, int> map;
for (int x = 0; x < 21; x++)
map[array1[x]]++;
/* Traverse map and find elements with prime frequencies and frequency at least k */
for (auto z : map)
{
if (PrimeOrNot(z.second) && z.second >= k)
cout << z.first << endl;
}
}
int main()
{
int array1[] = {5, 4, 7, 11, 23, 14, 5, 23, 45, 5, 7, 23, 11, 23, 11, 7, 7, 37, 7, 45};
int k = 3;
PrimeFrequency(array1, k);
return 0;
}

You can also try this code with Online C++ Compiler

Java program to find numbers with prime frequencies greater than or equal to k.

import java.util.*;
public class PrimeFrequency
{
/* Function to find numbers with prime frequencies greater than or equal to k. */
static void PrimeOccurr(int[] array1, int k)
{
Map<Integer, Integer> map = new HashMap<>();
for (int x = 0; x < array1.length; x++) {
int SetVal = array1[x];
int frequency;
if (map.containsKey(SetVal)) {
frequency = map.get(SetVal);
frequency++;
}
else
frequency = 1;
map.put(SetVal, frequency);
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int value = entry.getValue();
if (IsPrimeNum(value) && value >= k)
System.out.println(entry.getKey());
}
}
private static boolean IsPrimeNum(int z)
{
if ((z > 2 && z % 2 == 0) || z == 1)
return false;
for (int x = 3; x <= (int)Math.sqrt(z);x += 2) {
if (z % x == 0)
return false;
}
return true;
}
public static void main(String[] args)
{
int[] array1 = {5, 4, 7, 11, 23, 14, 5, 23, 45, 5, 7, 23, 11, 23, 11, 7, 7, 37, 7, 45};
int k = 3;
PrimeOccurr(array1, k);
}
}

You can also try this code with Online Java Compiler

Python program to find numbers with prime frequencies greater than or equal to k.

def PrimeFrequency(array1, k):
map = {}
# Insert values and their frequencies
for SetVal in array1:
frequency = 0
if SetVal in map :
frequency = map[SetVal]
frequency += 1
else :
frequency = 1
map[SetVal] = frequency
# Traverse map and find elements with prime frequencies and frequency at least k
for initial in map :
PrimeValue = map[initial]
if PrimeOrNot(PrimeValue) and PrimeValue >= k:
print(initial)
# Check if the number of occurrences are primes or not
def PrimeOrNot(x):
if (x > 2 and not x % 2) or x == 1:
return False
for z in range(3, int(x**0.5 + 1), 2):
if not x % z:
return False
return True
array1 = [ 5, 4, 7, 11, 23, 14, 5, 23, 45, 5, 7, 23, 11, 23, 11, 7, 7, 37, 7, 45 ]
k = 3
PrimeFrequency(array1, k)

You can also try this code with Online Python Compiler

Suppose we have n/k elements having frequency k, so the property of being a prime number will be checked every time. But checking the property of being a prime number takes only O(n) time. N is the occurrence of numbers. So in the worst case also, this given algorithm will give a similar performance. So the time complexity of the "Numbers with Prime frequencies greater than or equal to k" problem's algorithm will be O(N), where "N" is the counting of numbers in an array.

Space complexity

It is the space occupied by the algorithm with respect to the input. The space complexity of the "Numbers with Prime frequencies greater than or equal to k" problem's algorithm is O(N), where "N" is the counting of numbers in an array.

Keys of Hashtable can only be a unique value because Hashtable doesn’t allow any duplicate entry by structure.

What is an array?

An array is a data structure that holds similar data types at contiguous storage locations.

What is a modulus(%) operator?

The modulus operator is an arithmetic operator that is used to find the remainder of a division.

What is a Boolean operator?

A boolean operator is a type of operator which gives values either true or false.

What is the Time Complexity Numbers with Prime frequencies greater than or equal to k problem’s algorithm?

Time Complexity of Numbers with Prime frequencies greater than or equal to k problem’s algorithm is O(N).

Conclusion

"Numbers with Prime frequencies greater than or equal to k" problem can be solved using the Hashing technique. In this blog, we understood the problem statement with the help of an example, and we also learned about algorithms to solve the problem, solved the time and space complexity, and we implemented the algorithm using different programming languages.