#2521

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Distinct Prime Factors of Product of Array

Find the number of distinct prime factors in the product of an array of integers.

Problem Statement

Given an array of positive integers nums, return the number of distinct prime factors in the product of the elements of nums. The product of the array can be large, so avoid multiplying the elements directly.

To achieve this, consider prime factorization for each element in the array and track the distinct prime factors across all elements using an efficient method, such as a hash set.

Examples

Example 1

Input: nums = [2,4,3,7,10,6]

Output: 4

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

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 <= 104
2 <= nums[i] <= 1000

Solution Approach

Prime Factorization and Hashing

For each number in the array, factorize it into its prime factors. Use a hash table to store these factors, ensuring that each factor is counted only once.

Efficient Factorization with Sieve of Eratosthenes

Precompute the smallest prime factor (SPF) for each number up to the largest number in the array using the Sieve of Eratosthenes. This allows for faster prime factorization during the solution process.

Array Scanning and Set Lookup

Scan through the array and for each number, use the precomputed prime factors (via SPF) to extract all its prime factors. Add these to a set to automatically handle distinctness.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the sieve setup and the factorization process for each element. Sieve of Eratosthenes runs in O(n log log n) time, where n is the largest number in the array. Each number's prime factorization can be done in O(log m), where m is the number being factorized. Space complexity is mainly driven by the size of the sieve, O(n), and the hash set used for distinct primes.

What Interviewers Usually Probe

Candidate shows understanding of prime factorization methods.
Candidate leverages hash sets effectively to store distinct factors.
Candidate avoids directly multiplying large numbers, adhering to the problem's constraints.

Common Pitfalls or Variants

Common pitfalls

Directly multiplying the array elements, causing integer overflow or excessive computation time.
Failing to handle repeated prime factors correctly and undercounting them.
Not using efficient prime factorization methods like the Sieve of Eratosthenes, leading to slower solutions.

Follow-up variants

Consider an array of larger size or numbers near the upper constraint limit.
Extend to handle cases where the array contains numbers with repeated prime factors.
Optimize for scenarios where many numbers share common prime factors.

FAQ

How do I avoid multiplying large numbers in this problem?

Instead of multiplying all the numbers together, use prime factorization for each element and store the distinct prime factors in a set.

What is the best way to factorize numbers in this problem?

Using the Sieve of Eratosthenes to precompute the smallest prime factor for each number helps factorize numbers efficiently.

How do I handle repeated prime factors?

By using a hash set, you automatically ensure that only distinct prime factors are counted.

Can the array size affect performance?

Yes, larger arrays may require more time for scanning, but the sieve precomputation significantly speeds up factorization for each element.

What if the numbers in the array are large?

The sieve of Eratosthenes helps efficiently handle prime factorization for numbers up to 1000, which is the upper limit in this problem.

terminal

Solution

Solution 1: Hash Table + Prime Factorization

For each element in the array, first perform prime factorization on it, and then add the decomposed prime factors to the hash table. Finally, return the size of the hash table.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def distinctPrimeFactors(self, nums: List[int]) -> int:
        s = set()
        for n in nums:
            i = 2
            while i <= n // i:
                if n % i == 0:
                    s.add(i)
                    while n % i == 0:
                        n //= i
                i += 1
            if n > 1:
                s.add(n)
        return len(s)

Continue Practicing

#2584 split the array to make coprime products #2748 number of beautiful pairs #2001 number of pairs of interchangeable rectangles