Check if Any Element Has Prime Frequency - Practice Coding Problems

Check if Any Element Has Prime Frequency - Problem

Array Hash Table Math Counting Number Theory Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,6,4,6,4]

› Output: true

💡 Note: Element 4 appears 3 times and 3 is prime. Element 6 appears 2 times and 2 is prime. Since both frequencies are prime, return true.

Example 2 — No Prime Frequencies

$ Input: nums = [1,1,1,1]

› Output: false

💡 Note: Element 1 appears 4 times. 4 is not prime (divisible by 1, 2, and 4), so return false.

Example 3 — Single Element

$ Input: nums = [5]

› Output: false

💡 Note: Element 5 appears 1 time. 1 is not prime (prime numbers must be greater than 1), so return false.

Constraints

1 ≤ nums.length ≤ 1000
-1000 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array [4,6,4,6,4] with repeated elements

Process

Count frequencies: 4 appears 3 times, 6 appears 2 times

Output

Check primality: 3 is prime, 2 is prime → return true

Key Takeaway

🎯 Key Insight: Count element frequencies efficiently, then check each frequency for primality using square root optimization

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to count element frequencies efficiently using a hash map, then check each frequency for primality with optimized testing (only check divisors up to square root). Best approach is the frequency count method. Time: O(n + k√f), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n² × √f)	O(1)	Count frequencies manually, check primality by testing all divisors
Frequency Count with Hash Map	O(n + k√f)	O(n)	Use hash map to count frequencies efficiently, then check each for primality

Brute Force — Algorithm Steps

Count frequency of each element by scanning array multiple times
For each frequency, test all possible divisors to check primality
Return true if any frequency is prime

Visualization

Tap to expand

Step-by-Step Walkthrough

Select Element

Pick an element and count its occurrences

Check Primality

Test if frequency is prime by trying all divisors

Result

Return true if any frequency is prime

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

bool solution(int* nums, int numsSize) {
    bool processed[2001] = {false}; // Assuming nums[i] in reasonable range
    
    for (int i = 0; i < numsSize; i++) {
        int num = nums[i] + 1000; // Offset for negative numbers
        if (processed[num]) continue;
        processed[num] = true;
        
        // Count frequency
        int freq = 0;
        for (int j = 0; j < numsSize; j++) {
            if (nums[j] == nums[i]) freq++;
        }
        
        // Check if prime
        if (isPrime(freq)) return true;
    }
    
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int count = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[count++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    bool result = solution(nums, count);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × √f)

O(n²) for counting frequencies + O(√f) for each primality check where f is frequency

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables, no extra data structures

✓ Linear Space

8.5K Views

Medium Frequency

~12 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler