Difficulty: Easy | Acceptance: 62.50% | Paid: No Topics: Array, Hash Table, Math, Counting, Number Theory
You are given an array of positive integers nums. Return true if any element appears a prime number of times, otherwise return false.
- Examples
- Constraints
- Brute Force with Hash Map
- Optimized Prime Check
- Sieve of Eratosthenes
Examples
Example 1:
Input: nums = [1,2,3,4,5]
Output: false
Explanation: Each element appears exactly once, and 1 is not a prime number.
Example 2:
Input: nums = [1,2,3,2,3,3]
Output: true
Explanation: The element 2 appears 2 times (prime), and element 3 appears 3 times (prime).
Example 3:
Input: nums = [1,1,1,1,1,1]
Output: false
Explanation: The element 1 appears 6 times, and 6 is not a prime number.
Constraints
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
Brute Force with Hash Map
Intuition Count the frequency of each element using a hash map, then check if any frequency is a prime number by testing divisibility.
Steps
- Create a hash map to count occurrences of each element.
- For each frequency in the hash map, check if it’s prime.
- Return true if any frequency is prime, otherwise false.
python
class Solution:
def hasPrimeFrequency(self, nums: list[int]) -> bool:
from collections import Counter
def is_prime(n: int) -> bool:
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
freq = Counter(nums)
for count in freq.values():
if is_prime(count):
return True
return False
Complexity
- Time: O(n × √m) where n is array length and m is the maximum frequency
- Space: O(n) for the hash map
- Notes: Simple and straightforward approach.
Optimized Prime Check
Intuition Same as brute force but with optimized prime checking by handling edge cases and skipping even numbers.
Steps
- Count frequencies using a hash map.
- Use an optimized isPrime function that handles 2, even numbers, and only checks odd divisors.
- Return true if any frequency is prime.
python
class Solution:
def hasPrimeFrequency(self, nums: list[int]) -> bool:
from collections import Counter
def is_prime(n: int) -> bool:
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
for i in range(3, int(n ** 0.5) + 1, 2):
if n % i == 0:
return False
return True
freq = Counter(nums)
for count in freq.values():
if is_prime(count):
return True
return False
Complexity
- Time: O(n × √m) where n is array length and m is the maximum frequency
- Space: O(n) for the hash map
- Notes: About 2x faster than brute force for large numbers by skipping even divisors.
Sieve of Eratosthenes
Intuition Precompute all primes up to the maximum possible frequency (array length) using the Sieve of Eratosthenes, then check frequencies in O(1).
Steps
- Count frequencies using a hash map.
- Build a sieve of primes up to the array length.
- Check if any frequency is marked as prime in the sieve.
python
class Solution:
def hasPrimeFrequency(self, nums: list[int]) -> bool:
from collections import Counter
n = len(nums)
if n < 2:
return False
# Sieve of Eratosthenes
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
freq = Counter(nums)
for count in freq.values():
if is_prime[count]:
return True
return False
Complexity
- Time: O(n log log n + n) = O(n log log n) for sieve + counting
- Space: O(n) for the sieve array and hash map
- Notes: Best for large inputs with many unique frequencies, but uses more memory.