Distinct Prime Factors of Product of Array solution and explanation
Google
9 more videos on this problem
2521. Distinct Prime Factors of Product of Array HindiThinkCode · 5:37 · 1K views
Distinct Prime Factors of Product of Array | leetcode Weekly 326 | Leetcode MediumBinaryMagic · 9:13 · 839 views
2521. Distinct Prime Factors of Product of Array | Weekly Contest 326 | LeetCode | DCC NIT-ADCC NITA · 7:13 · 558 views
2521. Distinct Prime Factors of Product of Array (Leetcode Medium)Programming Live with Larry · 6:12 · 555 views
Leetcode Weekly contest 326 - Medium - Distinct Prime Factors of Product of ArrayPrakhar Agrawal · 5:04 · 494 views
2521. Distinct Prime Factors of Product of Array | LeetCode | C++ | Beginner Friendly SolutionDeep Tech · 10:37 · 280 views
Leetcode 2521: Distinct Prime Factors of Product of ArrayAlgorithms Casts · 15:39 · 269 views
Distinct Prime Factors of Product of Array || Leetcode Weekly 326 || Medium || C++Priyanshi Porwal · 8:10 · 252 views
Distinct Prime Factors of Product of ArrayTech Courses · 8:01 · 193 views
2521 Distinct Prime Factors of Product of Array | Leetcode Weekly Contest 326Ashutosh sharma · 8:40 · 158 views
The problem
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
1is called prime if it is divisible by only1and itself. - An integer
val1is a factor of another integerval2ifval2 / val1is 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] <= 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.
def countDistinctPrimeFactors(nums):
# Sieve of Eratosthenes to find all primes up to a certain number
def sieve(n):
is_prime = [True] * (n + 1)
p = 2
while p * p <= n:
if is_prime[p]:
for i in range(p * p, n + 1, p):
is_prime[i] = False
p += 1
return [p for p in range(2, n + 1) if is_prime[p]]
primes = sieve(1000)
distinct_primes = set()
for num in nums:
for prime in primes:
if prime * prime > num:
break
if num % prime == 0:
distinct_primes.add(prime)
while num % prime == 0:
num //= prime
if num > 1:
distinct_primes.add(num)
return len(distinct_primes)
# Example usage
nums = [2, 4, 3, 7, 10, 6]
print(countDistinctPrimeFactors(nums)) # Output: 4import java.util.HashSet;
import java.util.Set;
public class DistinctPrimeFactors {
private static Set<Integer> sieve(int n) {
boolean[] isPrime = new boolean[n + 1];
for (int i = 2; i <= n; i++) isPrime[i] = true;
for (int p = 2; p * p <= n; p++) {
if (isPrime[p]) {
for (int i = p * p; i <= n; i += p) isPrime[i] = false;
}
}
Set<Integer> primes = new HashSet<>();
for (int i = 2; i <= n; i++) {
if (isPrime[i]) primes.add(i);
}
return primes;
}
public static int countDistinctPrimeFactors(int[] nums) {
Set<Integer> primes = sieve(1000);
Set<Integer> distinctPrimes = new HashSet<>();
for (int num : nums) {
for (int prime : primes) {
if (prime * prime > num) break;
if (num % prime == 0) {
distinctPrimes.add(prime);
while (num % prime == 0) num /= prime;
}
}
if (num > 1) distinctPrimes.add(num);
}
return distinctPrimes.size();
}
public static void main(String[] args) {
int[] nums = {2, 4, 3, 7, 10, 6};
System.out.println(countDistinctPrimeFactors(nums)); // Output: 4
}
}using System;
using System.Collections.Generic;
class DistinctPrimes
{
private static HashSet<int> Sieve(int n)
{
bool[] isPrime = new bool[n + 1];
for (int i = 2; i <= n; i++) isPrime[i] = true;
for (int p = 2; p * p <= n; p++)
{
if (isPrime[p])
{
for (int i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
HashSet<int> primes = new HashSet<int>();
for (int i = 2; i <= n; i++)
{
if (isPrime[i]) primes.Add(i);
}
return primes;
}
public static int CountDistinctPrimeFactors(int[] nums)
{
var primes = Sieve(1000);
var distinctPrimes = new HashSet<int>();
foreach (var num in nums)
{
int current = num;
foreach (var prime in primes)
{
if (prime * prime > current) break;
if (current % prime == 0)
{
distinctPrimes.Add(prime);
while (current % prime == 0)
current /= prime;
}
}
if (current > 1) distinctPrimes.Add(current);
}
return distinctPrimes.Count;
}
static void Main()
{
int[] nums = { 2, 4, 3, 7, 10, 6 };
Console.WriteLine(CountDistinctPrimeFactors(nums));
}
}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.
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.
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.
function countDistinctPrimeFactors(nums) {
const getPrimeFactors = (n) => {
const factors = new Set();
let divisor = 2;
while (n >= 2) {
if (n % divisor === 0) {
factors.add(divisor);
n /= divisor;
} else {
divisor++;
}
}
return factors;
};
const distinctPrimes = new Set();
nums.forEach(num => {
const primeFactors = getPrimeFactors(num);
primeFactors.forEach(prime => {
distinctPrimes.add(prime);
});
});
return distinctPrimes.size;
}
// Example usage
const nums = [2, 4, 3, 7, 10, 6];
console.log(countDistinctPrimeFactors(nums)); // Output: 4#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
bool contains(int* arr, int size, int val) {
for (int i = 0; i < size; i++) {
if (arr[i] == val) return true;
}
return false;
}
int findDistinctPrimeFactors(int* nums, int n) {
int* distinctPrimes = (int*)malloc(n * sizeof(int));
int count = 0;
for (int i = 0; i < n; i++) {
int num = nums[i];
for (int p = 2; p * p <= num; p++) {
if (num % p == 0) {
if (!contains(distinctPrimes, count, p)) {
distinctPrimes[count++] = p;
}
while (num % p == 0) num /= p;
}
}
if (num > 1 && !contains(distinctPrimes, count, num)) {
distinctPrimes[count++] = num;
}
}
free(distinctPrimes);
return count;
}
int main() {
int nums[] = {2, 4, 3, 7, 10, 6};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", findDistinctPrimeFactors(nums, size)); // Output: 4
return 0;
}The JavaScript solution uses trial division for discovering the prime factors of each array element and stores them in a set to ensure uniqueness.
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.
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.
class Solution {
public:
int distinctPrimeFactors(vector<int>& nums) {
unordered_set<int> s;
for (int& n : nums) {
for (int i = 2; i <= n / i; ++i) {
if (n % i == 0) {
s.insert(i);
while (n % i == 0) {
n /= i;
}
}
}
if (n > 1) {
s.insert(n);
}
}
return s.size();
}
};function distinctPrimeFactors(nums: number[]): number {
const s: Set<number> = new Set();
for (let n of nums) {
let i = 2;
while (i <= n / i) {
if (n % i === 0) {
s.add(i);
while (n % i === 0) {
n = Math.floor(n / i);
}
}
++i;
}
if (n > 1) {
s.add(n);
}
}
return s.size;
}func distinctPrimeFactors(nums []int) int {
s := map[int]bool{}
for _, n := range nums {
for i := 2; i <= n/i; i++ {
if n%i == 0 {
s[i] = true
for n%i == 0 {
n /= i
}
}
}
if n > 1 {
s[n] = true
}
}
return len(s)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prime Factorization with Sieve | Time Complexity: O(n log log max) where max is the largest number in |
| 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 | – |
Complexity analysis
| 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 |
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.