Skip to main content
Talentd

Distinct Prime Factors of Product of Array - Solution & Explanation

MediumArrayHash TableMathNumber Theory9 min readAsked at: Meta, Google
Practice this problem

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

Approach Overview

Problem 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 1: Prime Factorization with Sieve

This approach utilizes the Sieve of Eratosthenes to precompute prime numbers up to 1000 (the maximum possible element in the array). For each element in the array nums, determine its prime factors using the precomputed prime list and track them using a set to ensure each factor is counted only once.

The Python solution precomputes all prime numbers up to 1000 using the Sieve of Eratosthenes. For each integer in the input nums, it determines its distinct prime factors and adds them to a set. Finally, it returns the size of the set as the number of distinct prime factors.

Code

PythonJavaC#

Python

Java

C#

Complexity

Time Complexity: O(n log log max) where max is the largest number in nums (1000 in this case), due to the sieve. Space Complexity: O(n) where n is the number of distinct primes.

Try this approach in the editor →

Approach 2: Prime Factorization with Trial Division

This approach uses trial division for prime factorization. For each element in the array, check divisibility starting from the smallest prime and record distinct primes in a set. This avoids the prerequisite computation of a list of primes.

The JavaScript solution uses trial division for discovering the prime factors of each array element and stores them in a set to ensure uniqueness.

Code

JavaScriptC

JavaScript

C

Complexity

Time Complexity: O(n sqrt(max)) assuming trial division up to the square root of each number. Space Complexity: O(n) for the distinct primes.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(n times \sqrt{m}), and the space complexity is O(\frac{m}{log m}). Where n and m are the length of the array and the maximum value in the array, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prime Factorization with Sieve

Time Complexity: O(n log log max) where max is the largest number in nums (1000 in this case), due to the sieve. Space Complexity: O(n) where n is the number of distinct primes.

Prime Factorization with Trial Division

Time Complexity: O(n sqrt(max)) assuming trial division up to the square root of each number. Space Complexity: O(n) for the distinct primes.

Hash Table + Prime Factorization—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prime Factorization with Trial DivisionO(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

Video Solution

2521. Distinct Prime Factors of Product of Array Hindi • ThinkCode • 1,371 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Distinct Prime Factors of Product of Array easy or hard?
LeetCode classifies this problem as Medium. The logic is straightforward once you recognize that you should factorize each number instead of computing the full product, but efficient factorization and understanding prime decomposition require some number theory knowledge.
Distinct Prime Factors of Product of Array Python/Java solution
In Python or Java, iterate through the array and factorize each number. Either perform trial division up to sqrt(n) or use a precomputed smallest prime factor array. Add each discovered prime to a HashSet (Java) or set (Python) and return the size of that set.
How to solve Distinct Prime Factors of Product of Array in O(n)?
An almost linear solution can be achieved by precomputing the smallest prime factor using a sieve. After the O(M log log M) preprocessing step, each element is factorized in logarithmic time by repeatedly dividing by its SPF. The distinct primes are stored in a hash set and counted at the end.
What is the best approach for Distinct Prime Factors of Product of Array?
The most efficient approach is prime factorization using a sieve that stores the smallest prime factor (SPF) for every number up to the maximum element. After preprocessing in O(M log log M), each number can be factorized quickly by repeated SPF lookups. Insert each prime factor into a set and return the set size.
Is Distinct Prime Factors of Product of Array asked at Google/Amazon/Meta?
Problems involving prime factorization and counting distinct factors appear in interviews at companies like Amazon, Google, and Meta, especially for roles testing number theory fundamentals and hashing techniques. Variations often involve factor counting, gcd relationships, or prime preprocessing.
What data structure is used in Distinct Prime Factors of Product of Array?
A hash set is used to store unique prime factors discovered during factorization. This ensures duplicates across different numbers are ignored while maintaining constant average-time insert and lookup operations.
What is the time complexity of Distinct Prime Factors of Product of Array?
Using trial division, the complexity is O(n * sqrt(m)) where n is the array size and m is the maximum value in the array. With a sieve-based smallest prime factor approach, preprocessing costs O(M log log M) and each factorization is near O(log m), making it faster for large datasets.

Ready to solve this problem?

Practice Distinct Prime Factors of Product of Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

2 Keys Keyboard

Next

Closest Divisors