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] <= 1000To solve #2521 Distinct Prime Factors of Product of Array, the key observation is that instead of computing the full product of the array (which could overflow), you only need the distinct prime factors that appear in the factorization of each element.
Iterate through every number in the array and perform prime factorization. For each number, repeatedly divide by possible factors starting from 2 up to sqrt(n). Whenever a prime factor is found, store it in a hash set to ensure uniqueness. Continue dividing the number until that factor is no longer present, then move to the next possible factor. If a remaining value greater than 1 exists, it is also a prime factor and should be added to the set.
By aggregating factors from all elements, the final answer is simply the size of the set. This avoids large integer multiplication and efficiently tracks unique primes. The factorization step dominates the runtime.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prime factorization with Hash Set | O(n * sqrt(m)) where m is the maximum value in the array | O(k) for storing distinct prime factors |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Do not multiply all the numbers together, as the product is too big to store.
Think about how each individual number's prime factors contribute to the prime factors of the product of the entire array.
Find the prime factors of each element in nums, and store all of them in a set to avoid duplicates.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Computing the full product can quickly exceed integer limits for large arrays or values. Instead, extracting prime factors from each number individually gives the same information without risking overflow.
Yes, variations of this problem appear in coding interviews because they test number theory fundamentals, prime factorization, and set usage. It also checks whether candidates avoid unnecessary large-number computations.
A hash set is the best data structure because it automatically removes duplicates and allows constant-time insert and lookup. This makes it ideal for tracking distinct prime factors across all numbers in the array.
The optimal approach is to factorize each number in the array and store all discovered prime factors in a hash set. This avoids computing the full product and ensures only unique primes are counted. The final answer is the size of the set.