Numbers with prime frequencies greater than or equal to k

Problem Statement

Problem “Numbers with prime frequencies greater than or equal to k” states that you are given an array of integers size n and an integer value k. All the numbers inside it are prime numbers. The problem statement asks to find out the numbers which appear in the array at least k times and a prime number of times in the array.

Example

arr[] = {29, 11, 37, 53, 53, 53, 29, 53, 29, 53}, k = 2

29 and 53

Explanation: 29 and 53 appear 3 times and 5 times respectively which also satisfies the condition to appear at least k times.

Algorithm to find numbers with prime frequencies greater than or equal to k

1. Declare a map and store all the numbers of the array in the map with their frequencies.
2. Traverse the map.
    1. Check if the frequency of each element is at least k or greater than k.
    2. Find if that frequency is a prime number or not.
    3. If the frequency is a prime number then print that key else go for other numbers.

Explanation

We have given an array of integers and a value k. All the numbers given are also primary, we have asked to find out if the number appears at least k times and also any prime number times in the array, then print that number. To solve this, we will be using the Hashing method. We will use a Map. Our task is to find the appearance of a number, it means we have to find the occurrence of each element, to resolve this we are going to use a Map.

We will traverse the array and count and store each element and its frequency into the map. If the number is a new entry in the map, then make a place for it in the map and mark its frequency as 1. If it already exists, then simply get its frequency and increase its frequency by 1 and again insert that frequency along with its number. In this way, we can count all the frequencies of each number. Now we need to check if the frequency of each number, firstly exists k number of times and also the number of times is appearing should be a prime number.

For that case, we will be traversing each key in a map, and get its frequency. We have made a function which checks that if the frequency is a prime number or not. For prime number, it should not be 1, and also it should not be divisible by another number than itself. If it is divisible by any number then return false. If it is divisible then print that key means number of that frequency, and proceed further for another number.

Code

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

#include<iostream>
#include<unordered_map>

using namespace std;

bool checkIfPrime(int n)
{
    if (n <= 1)
        return false;

    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return false;

    return true;
}
void numberWithPrimeFreq(int arr[], int k)
{
    unordered_map<int, int> MAP;

    for (int i = 0; i < 12; i++)
        MAP[arr[i]]++;

    for (auto x : MAP)
    {
        if (checkIfPrime(x.second) && x.second >= k)
            cout << x.first << endl;
    }
}
int main()
{
    int arr[] = { 29,11,37,53,53,53,29,53,29,53 };
    int k = 2;

    numberWithPrimeFreq(arr, k);
    return 0;
}

29
53

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

import java.util.HashMap;
import java.util.Map;

public class  Frequencies_PrimeNumber
{
  public static void numberWithPrimeFreq(int[] arr, int k)
  {
    Map<Integer, Integer> MAP = new HashMap<>();

    for (int i = 0; i < arr.length; i++)
    {
      int val = arr[i];

      int freq;
      if (MAP.containsKey(val))
      {
        freq = MAP.get(val);
        freq++;
      }
      else
        freq = 1;
      MAP.put(val, freq);
    }
    for (Map.Entry<Integer, Integer> entry :MAP.entrySet())
    {
      int TEMP = entry.getValue();
      if (checkIfPrime(TEMP) && TEMP >= k)
        System.out.println(entry.getKey());
    }
  }
  private static boolean checkIfPrime(int n)
  {
    if ((n > 2 && n % 2 == 0) || n == 1)
      return false;

    for (int i = 2 ; i <n;	i ++)
    {
      if (n % i == 0)
        return false;
    }
    return true;
  }
  public static void main(String[] args)
  {
    int[] arr = { 29,11,37,53,53,53,29,53,29,53 };
    int k = 2;

    numberWithPrimeFreq(arr, k);
  }
}

53
29

Complexity Analysis

Time Complexity

Here, consider we have n/k elements with frequency k, so every time primality will be checked. But the primality checking takes only O(n) time. Here n is the frequency. So even in the worst case, the whole algorithm can run in linear time. O(N) where “N”  is the number of elements in the array.

Space Complexity

Because of the space required for storing the input, O(N) where “N”  is the number of elements in the array.