3591. Check if Any Element Has Prime Frequency

EasyArrayHash TableMathCountingNumber Theory

Leetcode Link

Problem 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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve the problem, it helps to first realize that what matters is not the actual elements of the array, but how many times each unique number occurs. If any of these counts (frequencies) is a prime number, the answer should be true. So the first step is to count how often each number appears. Once we have these frequencies, we just need to check if any of them is prime. This reduces the original problem to checking the primality of a small set of numbers.

Solution Approach

First, use a hash table (such as a Counter in Python) to count how many times each element appears in the array. This gives the frequency for every unique value in nums.

After building the frequency table, loop through the frequency values. For each frequency, check if it is a prime number:

A number is prime if it's greater than 1 and has no divisors other than 1 and itself.
To check if a number x is prime, test if it's divisible by any integer from 2 to sqrt(x). If you find a divisor in this range, then x is not prime. Otherwise, it's prime.

Return true if you find any frequency that is prime. If no frequencies are prime, return false.

This approach efficiently combines counting with prime checking for the solution.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the input array: nums = [4, 2, 2, 4, 4, 3].

Step 1: Count frequencies Count how many times each unique element appears:

4 appears 3 times
2 appears 2 times
3 appears 1 time

So, the frequency table looks like: {4: 3, 2: 2, 3: 1}

Step 2: Check each frequency for primality

Frequency 3: 3 is greater than 1 and its only divisors are 1 and 3, so 3 is prime.
Frequency 2: 2 is greater than 1 and only divisible by 1 and 2, so 2 is prime.
Frequency 1: 1 is not a prime number.

Since at least one frequency (both 2 and 3) is prime, return true.

Summary: Count the element frequencies, check if any is prime, and return true if so, else false.

Solution Implementation

1from typing import List
2from collections import Counter
3from math import sqrt
4
5class Solution:
6    def checkPrimeFrequency(self, nums: List[int]) -> bool:
7        # Helper function to check if a number is prime
8        def is_prime(x: int) -> bool:
9            if x < 2:
10                return False
11            # A number x is prime if no number in [2, sqrt(x)] divides x
12            for i in range(2, int(sqrt(x)) + 1):
13                if x % i == 0:
14                    return False
15            return True
16
17        # Count the frequency of each element in nums
18        frequency = Counter(nums)
19
20        # Check if any frequency is a prime number
21        return any(is_prime(count) for count in frequency.values())
22

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    // Checks if any frequency of the elements is a prime number
6    public boolean checkPrimeFrequency(int[] nums) {
7        Map<Integer, Integer> countMap = new HashMap<>();
8
9        // Count the frequency of each element in the array
10        for (int num : nums) {
11            countMap.merge(num, 1, Integer::sum);
12        }
13
14        // Check if any frequency is a prime number
15        for (int frequency : countMap.values()) {
16            if (isPrime(frequency)) {
17                return true;
18            }
19        }
20
21        return false;
22    }
23
24    // Determines if a given number is a prime number
25    private boolean isPrime(int number) {
26        if (number < 2) {
27            return false;
28        }
29        // Only check divisibility up to the square root of the number
30        for (int i = 2; i * i <= number; i++) {
31            if (number % i == 0) {
32                return false;
33            }
34        }
35        return true;
36    }
37}
38

1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7    // Checks if any number in 'nums' appears a prime number of times
8    bool checkPrimeFrequency(vector<int>& nums) {
9        unordered_map<int, int> countMap; // Map to store frequency of each number
10
11        // Count frequency of each number in nums
12        for (int num : nums) {
13            ++countMap[num];
14        }
15
16        // Check if any frequency is a prime number
17        for (const auto& [number, frequency] : countMap) {
18            if (isPrime(frequency)) {
19                return true; // Found a prime frequency
20            }
21        }
22        return false; // No prime frequency found
23    }
24
25private:
26    // Helper function to determine if a number is prime
27    bool isPrime(int number) {
28        if (number < 2) {
29            return false; // Numbers less than 2 are not prime
30        }
31        for (int divisor = 2; divisor * divisor <= number; ++divisor) {
32            if (number % divisor == 0) {
33                return false; // Found a divisor, number is not prime
34            }
35        }
36        return true; // Number is prime
37    }
38};
39

1/**
2 * Check if there is any number in the input array `nums`
3 * whose frequency is a prime number.
4 * @param nums Array of numbers to check.
5 * @returns True if at least one number's frequency is prime, otherwise false.
6 */
7function checkPrimeFrequency(nums: number[]): boolean {
8    // Count the frequency of each number in `nums`
9    const frequencyMap: Record<number, number> = {};
10
11    for (const num of nums) {
12        // Increment the count for each number
13        frequencyMap[num] = (frequencyMap[num] || 0) + 1;
14    }
15
16    // Check if any frequency value is a prime number
17    for (const freq of Object.values(frequencyMap)) {
18        if (isPrime(freq)) {
19            return true;
20        }
21    }
22
23    return false;
24}
25
26/**
27 * Check if a given number `n` is a prime number.
28 * @param n Number to check.
29 * @returns True if `n` is a prime number, otherwise false.
30 */
31function isPrime(n: number): boolean {
32    // 0 and 1 are not primes
33    if (n < 2) {
34        return false;
35    }
36
37    // Check for factors up to the square root of n
38    for (let i = 2; i * i <= n; i++) {
39        if (n % i === 0) {
40            return false;
41        }
42    }
43
44    return true;
45}
46

Time and Space Complexity

Time Complexity: O(n × √M) Where n is the length of the input array nums, and M is the maximum possible frequency count of any element in nums.
- Building the frequency counter with Counter(nums) takes O(n).
- For each unique element (at most n), we check if its count is prime.
- Checking if a number x is prime takes O(√x) time.
- In the worst case, there are O(n) unique elements, and the maximum frequency (up to n) may require up to O(√n) time to check for primality, resulting in an overall complexity of O(n × √M).
Space Complexity: O(n)
- The frequency counter uses space up to O(n) for the worst case (all elements in nums are unique).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: