3591. Check if Any Element Has Prime Frequency

SourceWeekly Contest 455 Q1DifficultyEasyRating1234

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.

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

Solutions

Solution 1: Counting + Prime Check

Thinking

We only need whether some value’s frequency is prime. Count first, then trial-divide each frequency.

A frequency is at most \(n\), so testing up to its square root is enough. Return true on the first prime frequency.

We use a hash table \(\text{cnt}\) to count the frequency of each element. Then, we iterate through the values in \(\text{cnt}\) and check if any of them is a prime number. If there is a prime, return true; otherwise, return false.

The time complexity is \(O(n \times \sqrt{M})\), and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\text{nums}\) and \(M\) is the maximum

Python3JavaC++GoTypeScript

class Solution:
    def checkPrimeFrequency(self, nums: List[int]) -> bool:
        def is_prime(x: int) -> bool:
            if x < 2:
                return False
            return all(x % i for i in range(2, int(sqrt(x)) + 1))

        cnt = Counter(nums)
        return any(is_prime(x) for x in cnt.values())

import java.util.*;

class Solution {
    public boolean checkPrimeFrequency(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) {
            cnt.merge(x, 1, Integer::sum);
        }

        for (int x : cnt.values()) {
            if (isPrime(x)) {
                return true;
            }
        }
        return false;
    }

    private boolean isPrime(int x) {
        if (x < 2) {
            return false;
        }
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    bool checkPrimeFrequency(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for (int x : nums) {
            ++cnt[x];
        }

        for (auto& [_, x] : cnt) {
            if (isPrime(x)) {
                return true;
            }
        }
        return false;
    }

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

func checkPrimeFrequency(nums []int) bool {
    cnt := make(map[int]int)
    for _, x := range nums {
        cnt[x]++
    }
    for _, x := range cnt {
        if isPrime(x) {
            return true
        }
    }
    return false
}

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

function checkPrimeFrequency(nums: number[]): boolean {
    const cnt: Record<number, number> = {};
    for (const x of nums) {
        cnt[x] = (cnt[x] || 0) + 1;
    }
    for (const x of Object.values(cnt)) {
        if (isPrime(x)) {
            return true;
        }
    }
    return false;
}

function isPrime(x: number): boolean {
    if (x < 2) {
        return false;
    }
    for (let i = 2; i * i <= x; i++) {
        if (x % i === 0) {
            return false;
        }
    }
    return true;
}

3591. Check if Any Element Has Prime Frequency

Description

Solutions

Solution 1: Counting + Prime Check

Comments