Problem statement

You are given an integer array nums.

Return true if the number of occurrences of some element of nums is a prime number, and false otherwise.

A prime number is a natural number greater than 1 whose only divisors are 1 and itself.

Example 1

Input: nums = [7,3,7,9,7]
Output: true
Explanation: `7` occurs 3 times, and 3 is prime.

Example 2

Input: nums = [1,2,3,4]
Output: false
Explanation: Every element occurs once, and 1 is not prime.

Example 3

Input: nums = [6,6,6,6]
Output: false
Explanation: `6` occurs 4 times, and 4 is not prime.

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

Hints for Check if Any Element Has Prime Frequency

1. Hint 1

   Count how many times each value occurs.

2. Hint 2

   Test each count for primality by trial division up to its square root — counts are at most 100.

How to solve Check if Any Element Has Prime Frequency

Build the frequency table, then ask whether any frequency is prime.

Approach

1. Count the occurrences of each value (an array of 101 counters suffices).
2. For each non-zero count c, test whether c is prime: c >= 2 and no d with 2 <= d * d <= c divides it.
3. Return true on the first prime count, false if there is none.

Why it works

The table holds exactly the frequency of every element, and trial division up to sqrt(c) decides primality because any composite number has a divisor no larger than its square root.

Complexity

• Time — O(n + V * sqrt(n))
• Space — O(V) with V = 101

Pitfalls

• 1 is not prime, so an array of distinct values answers false.
• Test the frequencies, not the values themselves.

Reference solution

Python

from typing import List

def checkPrimeFrequency(nums: List[int]) -> bool:
    def is_prime(x: int) -> bool:
        if x < 2:
            return False
        d = 2
        while d * d <= x:
            if x % d == 0:
                return False
            d += 1
        return True

    count = {}
    for v in nums:
        count[v] = count.get(v, 0) + 1
    return any(is_prime(c) for c in count.values())

Java

static boolean isPrimeCount(int x) {
    if (x < 2) return false;
    for (int d = 2; d * d <= x; d++) if (x % d == 0) return false;
    return true;
}

public static boolean checkPrimeFrequency(int[] nums) {
    int[] count = new int[101];
    for (int v : nums) count[v]++;
    for (int c : count) if (isPrimeCount(c)) return true;
    return false;
}

C++

bool isPrimeCount(int x) {
    if (x < 2) return false;
    for (int d = 2; d * d <= x; d++) if (x % d == 0) return false;
    return true;
}

bool checkPrimeFrequency(vector<int>& nums) {
    vector<int> count(101, 0);
    for (int v : nums) count[v]++;
    for (int c : count) if (isPrimeCount(c)) return true;
    return false;
}

JavaScript

var checkPrimeFrequency = function(nums) {
    var count = new Array(101).fill(0);
    for (var i = 0; i < nums.length; i++) count[nums[i]]++;
    for (var v = 0; v <= 100; v++) if (isPrimeCount(count[v])) return true;
    return false;
};

var isPrimeCount = function(x) {
    if (x < 2) return false;
    for (var d = 2; d * d <= x; d++) if (x % d === 0) return false;
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy