Skip to main content

2521 - Distinct Prime Factors of Product of Array (Medium)

https://leetcode.com/problems/distinct-prime-factors-of-product-of-array/

Problem Statement​

Given an array of positive integers nums, return the number of distinct prime factors in the product of the elements of nums.

Note that:

  • A number greater than 1 is called prime if it is divisible by only 1 and itself.
  • An integer val1 is a factor of another integer val2 if val2 / val1 is an integer.

Example 1:

Input: nums = [2,4,3,7,10,6]
Output: 4
Explanation:
The product of all the elements in nums is: 2 * 4 * 3 * 7 * 10 * 6 = 10080 = 25 * 32 * 5 * 7.
There are 4 distinct prime factors so we return 4.

Example 2:

Input: nums = [2,4,8,16]
Output: 1
Explanation:
The product of all the elements in nums is: 2 * 4 * 8 * 16 = 1024 = 210.
There is 1 distinct prime factor so we return 1.

Constraints:

  • 1 <= nums.length <= 10^4
  • 2 <= nums[i] <= 1000

Approach 1: Prime Factorization + Set​

For each number, we can prime-factorize it and insert it to a Set. The answer would be the number of the size of set.

Written by @wingkwong
class Solution {
public:
    vector<pair<long long, int>> prime_factorize(long long n) {
        assert(n >= 1);
        vector<pair<long long, int>> result;

        auto extract = [&](long long p) {
            if (n % p == 0) {
                result.emplace_back(p, 0);

                do {
                    n /= p;
                    result.back().second++;
                } while (n % p == 0);
            }
        };

        for (long long p = 2; p * p <= n; p += p % 2 + 1)
            extract(p);

        if (n > 1)
            result.emplace_back(n, 1);

        return result;
    }

    int distinctPrimeFactors(vector<int>& nums) {
        set<int> s;
        for (auto x : nums) {
            for (auto x : prime_factorize(x)) {
                s.insert(x.first);
            }
        }
        return s.size();
    }
};