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.

Description Hints 3 Solution Video 5:37

2521. Distinct Prime Factors of Product of Array

Medium55.5% acceptance2 companies

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 = 2⁵ * 3² * 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 = 2¹⁰.
There is 1 distinct prime factor so we return 1.

Constraints:

1 <= nums.length <= 10⁴
2 <= nums[i] <= 1000

Asked at 2 companies

Google Meta

Topics

Hints open one at a time

Hint 1

Do not multiply all the numbers together, as the product is too big to store.

Hint 2

Think about how each individual number's prime factors contribute to the prime factors of the product of the entire array.

Hint 3

Find the prime factors of each element in nums, and store all of them in a set to avoid duplicates.

5:37

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution