703229. Numbers with prime frequencies greater than or equal to k
Numbers with prime frequencies greater than or equal to k
Summary
Given a list of integers, find all numbers that have prime frequencies greater than or equal to k. A frequency is considered prime if it's not divisible by any number except for 1 and the number itself. For example, if we have the list [2, 3, 4, 5], the prime frequencies are 1, 1, 2, and 1 respectively. The output should include all numbers from the original list that have a prime frequency greater than or equal to k.
Detailed Explanation
To solve this problem, we can first calculate the frequency of each number in the list. Then, for each frequency, check if it's prime by iterating from 2 to the square root of the frequency and checking if it's divisible by any of these numbers. If a frequency is not prime, we skip it. Finally, return all numbers that have a prime frequency greater than or equal to k.
Here's a step-by-step breakdown of the solution:
- Initialize an empty list to store the results.
- Iterate through the input list and calculate the frequency of each number.
- For each frequency, check if it's prime by iterating from 2 to the square root of the frequency.
- If the frequency is not divisible by any of these numbers (except for 1 and the frequency itself), consider it prime.
- Add all numbers that have a prime frequency greater than or equal to
kto the result list.
Time complexity: O(n log n) where n is the length of the input list, as we're iterating through the list once and then checking if each frequency is prime. Space complexity: O(n) for storing the results.
Optimized Solutions
Java
import java.util.*;
public class Main {
public static List<Integer> numbersWithPrimeFrequencies(int[] arr, int k) {
Map<Integer, Integer> frequencyMap = new HashMap<>();
List<Integer> result = new ArrayList<>();
for (int num : arr) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
int freq = entry.getValue();
boolean isPrime = true;
if (freq < 2) continue;
for (int i = 2; i * i <= freq; i++) {
if (freq % i == 0) {
isPrime = false;
break;
}
}
if (isPrime && freq >= k) result.add(entry.getKey());
}
return result;
}
}