Is Check if Any Element Has Prime Frequency easy or hard?

This problem is typically classified as Easy because it combines two straightforward steps: frequency counting and a simple prime number check. The challenge lies mainly in recognizing that only the counts matter, not the element values.

Check if Any Element Has Prime Frequency Python/Java solution

In Python, use collections.Counter or a dictionary to count elements, then run a helper function that checks divisibility up to √n. In Java, use HashMap to store counts and implement a small isPrime method. The same logic translates directly to C++, Go, and TypeScript.

How to solve Check if Any Element Has Prime Frequency in O(n)?

Traverse the array once to build a frequency map using a hash table. After counting, iterate over the frequency values and check whether any count is prime using a divisor check up to √count. The counting step dominates the runtime, making the algorithm effectively linear for typical inputs.

What is the best approach for Check if Any Element Has Prime Frequency?

The most efficient approach is counting element frequencies with a hash map and then checking whether any frequency is prime. Counting takes O(n) time, and each primality check costs O(√f) where f is the frequency. Space complexity is O(k) for k distinct elements. This is the standard solution expected in interviews.

Is Check if Any Element Has Prime Frequency asked at Google/Amazon/Meta?

Problems involving frequency counting and prime checks commonly appear in coding interviews at companies like Amazon and Google. They test familiarity with hash tables, basic number theory, and the ability to separate counting logic from validation logic.

What data structure is used in Check if Any Element Has Prime Frequency?

A hash table (hash map) is the primary data structure used to count occurrences of each element in the array. After building the map, simple arithmetic checks determine whether any frequency value is prime.

What is the time complexity of Check if Any Element Has Prime Frequency?

Building the frequency map requires O(n) time where n is the array length. Each frequency is then tested for primality using a square root check, which takes O(√f). Overall complexity is O(n + k√f), where k is the number of unique elements.

Description Hints 2 Solution Video 3:13

3591. Check if Any Element Has Prime Frequency

Easy62.6% acceptance

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

Topics

Hints open one at a time

Hint 1

Implement a function to check if a number is prime

Hint 2

Find the frequencies of all the distinct elements in the array (using data structures like map in C++), check if there is any element with prime frequency

3:13

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def checkPrimeFrequency(self, nums: List[int]) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2,3,4,5,4]

Input

[1,2,3,4,5]

Input

[2,2,2,4,4]

Your code is saved on this device.Solution