Welcome to Subscribe On Youtube
3591. Check if Any Element Has Prime Frequency
Description
You are given an integer array nums
.
Return true
if the frequency of any element of the array is prime, otherwise, return false
.
The frequency of an element x
is the number of times it occurs in the array.
A prime number is a natural number greater than 1 with only two factors, 1 and itself.
Example 1:
Input: nums = [1,2,3,4,5,4]
Output: true
Explanation:
4 has a frequency of two, which is a prime number.
Example 2:
Input: nums = [1,2,3,4,5]
Output: false
Explanation:
All elements have a frequency of one.
Example 3:
Input: nums = [2,2,2,4,4]
Output: true
Explanation:
Both 2 and 4 have a prime frequency.
Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 100
Solutions
Solution 1: Counting + Prime Check
We use a hash table $\text{cnt}$ to count the frequency of each element. Then, we iterate through the values in $\text{cnt}$ and check if any of them is a prime number. If there is a prime, return true
; otherwise, return false
.
The time complexity is $O(n \times \sqrt{M})$, and the space complexity is $O(n)$, where $n$ is the length of the array $\text{nums}$ and $M$ is the maximum
-
import java.util.*; class Solution { public boolean checkPrimeFrequency(int[] nums) { Map<Integer, Integer> cnt = new HashMap<>(); for (int x : nums) { cnt.merge(x, 1, Integer::sum); } for (int x : cnt.values()) { if (isPrime(x)) { return true; } } return false; } private boolean isPrime(int x) { if (x < 2) { return false; } for (int i = 2; i <= x / i; i++) { if (x % i == 0) { return false; } } return true; } }
-
class Solution { public: bool checkPrimeFrequency(vector<int>& nums) { unordered_map<int, int> cnt; for (int x : nums) { ++cnt[x]; } for (auto& [_, x] : cnt) { if (isPrime(x)) { return true; } } return false; } private: bool isPrime(int x) { if (x < 2) { return false; } for (int i = 2; i <= x / i; ++i) { if (x % i == 0) { return false; } } return true; } };
-
class Solution: def checkPrimeFrequency(self, nums: List[int]) -> bool: def is_prime(x: int) -> bool: if x < 2: return False return all(x % i for i in range(2, int(sqrt(x)) + 1)) cnt = Counter(nums) return any(is_prime(x) for x in cnt.values())
-
func checkPrimeFrequency(nums []int) bool { cnt := make(map[int]int) for _, x := range nums { cnt[x]++ } for _, x := range cnt { if isPrime(x) { return true } } return false } func isPrime(x int) bool { if x < 2 { return false } for i := 2; i*i <= x; i++ { if x%i == 0 { return false } } return true }
-
function checkPrimeFrequency(nums: number[]): boolean { const cnt: Record<number, number> = {}; for (const x of nums) { cnt[x] = (cnt[x] || 0) + 1; } for (const x of Object.values(cnt)) { if (isPrime(x)) { return true; } } return false; } function isPrime(x: number): boolean { if (x < 2) { return false; } for (let i = 2; i * i <= x; i++) { if (x % i === 0) { return false; } } return true; }