Watch 10 video solutions for Distinct Prime Factors of Product of Array, a medium level problem involving Array, Hash Table, Math. This walkthrough by ThinkCode has 1,316 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array of positive integers nums, return the number of distinct prime factors in the product of the elements of nums.
Note that:
1 is called prime if it is divisible by only 1 and itself.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 <= 1042 <= nums[i] <= 1000Problem Overview: You are given an integer array nums. Multiply all numbers conceptually and return how many distinct prime factors appear in that product. Instead of computing the full product (which quickly overflows), factorize each number and track unique primes.
Approach 1: Prime Factorization with Trial Division (O(n * sqrt(m)) time, O(k) space)
Iterate through every value in nums and factorize it using trial division. For each number, repeatedly divide by 2, then test odd divisors up to sqrt(num). Every time you find a prime factor, insert it into a hash set to ensure uniqueness. If the remaining value after division is greater than 1, it is also a prime factor and should be added to the set. The final answer is the size of the set. This approach is simple and works well when numbers are small, but repeated sqrt factorization becomes expensive for large inputs.
Approach 2: Prime Factorization with Sieve (O(M log log M + total factors) time, O(M) space)
Precompute the smallest prime factor (SPF) for every number up to the maximum value in nums using a sieve. This preprocessing step is similar to the Sieve of Eratosthenes but stores the smallest prime divisor for each number. Once the SPF array is built, factorizing any number becomes fast: repeatedly divide by spf[x] and insert each prime into a hash set. Since factorization reduces the number quickly, the total work across the array stays small. This approach is ideal when the input contains many numbers or when the maximum value is moderately large.
Both solutions rely on tracking unique primes with a set (a common pattern when working with Hash Table problems). The main difference is how quickly each number is factorized. Trial division performs direct divisor checks, while the sieve converts factorization into repeated array lookups.
Conceptually, the task belongs to Number Theory combined with simple iteration over an Array. The key insight: the distinct primes in the product are simply the union of prime factors from every element.
Recommended for interviews: Trial division is often sufficient and easy to explain during interviews. It demonstrates understanding of prime factorization and set-based deduplication. The sieve-based solution shows stronger algorithmic depth and is preferable when constraints push trial division toward time limits.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prime Factorization with Trial Division | O(n * sqrt(m)) | O(k) | Best for small numbers or quick interview implementation |
| Prime Factorization with Sieve (Smallest Prime Factor) | O(M log log M + total factors) | O(M) | Efficient when many numbers need factorization or max value is known |