Numbers with prime frequencies greater than or equal to k

Algorithm

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

1. Declare a map.
    
2. Store array data in the map along with their frequencies.
    
3. Traverse the map:
   
   
   1. For each element check if frequency >= k.
       
   2. Check If the frequency is a prime number or not.
       
   3. If the frequency is a prime number then print the key value.
       
4. 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

Run Code

OUTPUT

Code in Java 💻

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

Run Code

OUTPUT

Code in Python 💻

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

Run Code

OUTPUT

You can also read about the Longest Consecutive Sequence.

Complexities

Time Complexity

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.

Check out this problem - Find Duplicate In Array

Frequently Asked Questions

Does Hashtable allow duplicate entry of keys?

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.

Also read,

• Find all pairs (a,b) in an array such that a%b=k
• Count Divisible Pairs in an Array 
• Minimum number of Subsets with Distinct Elements

Refer to our guided paths on Coding Ninjas Studio to learn more about C programming, DSA, JavaScript, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Learning!