LeetCode 2521: Distinct Prime Factors of Product of Array

Explanation

To solve this problem, we need to calculate the product of all elements in the given array nums, find the prime factors of this product, and then count the distinct prime factors. We can achieve this by iterating over the elements in the array, calculating the product, finding the prime factors, and finally counting the distinct prime factors.

1. Create a helper function to find all prime factors of a number.
2. Calculate the product of all elements in the array.
3. Find the prime factors of the product.
4. Count the distinct prime factors found.

Time Complexity: O(n * sqrt(max_value)) where n is the number of elements in the array and max_value is the maximum value in the array. Space Complexity: O(sqrt(max_value)) for storing prime factors.

import java.util.*;

class Solution {
    public int distinctPrimeFactors(int[] nums) {
        Set<Integer> primeFactors = new HashSet<>();
        for (int num : nums) {
            for (int factor : findPrimeFactors(num)) {
                primeFactors.add(factor);
            }
        }
        return primeFactors.size();
    }

    private List<Integer> findPrimeFactors(int num) {
        List<Integer> factors = new ArrayList<>();
        for (int i = 2; i <= Math.sqrt(num); i++) {
            while (num % i == 0) {
                factors.add(i);
                num /= i;
            }
        }
        if (num > 1) {
            factors.add(num);
        }
        return factors;
    }
}