Distinct Prime Factors of Product of Array — Solution
Distinct Prime Factors of Product of Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Distinct Prime Factors of Product of Array is a medium coding problem on arrays, hash table and math, asked in Amazon and TCS interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Math, Number Theory
- Asked at: Amazon, TCS
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of positive integers nums, return the number of distinct prime factors of the product of all its elements.
A prime factor of x is a prime number that divides x. The product itself can be astronomically large — you never need to compute it.
Example 1
Input: nums = [6,10,15]
Output: 3
Explanation: The product 900 = 2² · 3² · 5² has the prime factors 2, 3 and 5.
Example 2
Input: nums = [16,32,8]
Output: 1
Explanation: Every element is a power of 2.
Example 3
Input: nums = [7,11,77,49]
Output: 2
Constraints
1 <= nums.length <= 10^42 <= nums[i] <= 1000
Hints for Distinct Prime Factors of Product of Array
Hint 1
A prime divides a product exactly when it divides at least one of the factors.
Hint 2
So the answer is the number of distinct primes that divide at least one element.
Hint 3
Factor each element by trial division up to its square root and collect the primes in a set.
How to solve Distinct Prime Factors of Product of Array
A prime divides the product if and only if it divides one of the elements (Euclid's lemma), so collect the prime factors of every element in a set.
Approach
- For each element
v, try divisorsd = 2, 3, …whiled·d <= v. - When
ddividesv, recorddand divide it out completely. - If
v > 1remains afterwards, it is a prime factor too; record it. - Return the number of distinct primes recorded.
Why it works
Euclid's lemma says a prime dividing a·b divides a or b, so the primes of the product are exactly the union of the elements' primes. In trial division, dividing each found factor out completely guarantees every later divisor that succeeds is prime, and whatever is left above 1 after d·d > v has no divisor up to its square root, so it is prime.
Complexity
- Time —
O(n · √V) with V = 1000 - Space —
O(number of primes ≤ V)
Pitfalls
- Never multiply the elements together — 10^4 numbers up to 1000 overflow anything.
- Do not forget the leftover factor greater than √v (for example 997, or the 7 in 14).
- Count primes, not prime powers: 8 contributes only 2.
Reference solution
Python
from typing import List
def distinctPrimeFactors(nums: List[int]) -> int:
primes = set()
for x in nums:
v = x
d = 2
while d * d <= v:
if v % d == 0:
primes.add(d)
while v % d == 0:
v //= d
d += 1
if v > 1:
primes.add(v)
return len(primes)Java
public static int distinctPrimeFactors(int[] nums) {
boolean[] seen = new boolean[1001];
int count = 0;
for (int x : nums) {
int v = x;
for (int d = 2; d * d <= v; d++) {
if (v % d == 0) {
if (!seen[d]) { seen[d] = true; count++; }
while (v % d == 0) v /= d;
}
}
if (v > 1 && !seen[v]) { seen[v] = true; count++; }
}
return count;
}C++
int distinctPrimeFactors(vector<int>& nums) {
set<int> primes;
for (int x : nums) {
int v = x;
for (int d = 2; d * d <= v; d++) {
if (v % d == 0) {
primes.insert(d);
while (v % d == 0) v /= d;
}
}
if (v > 1) primes.insert(v);
}
return primes.size();
}JavaScript
var distinctPrimeFactors = function(nums) {
var primes = new Set();
for (var i = 0; i < nums.length; i++) {
var v = nums[i];
for (var d = 2; d * d <= v; d++) {
if (v % d === 0) {
primes.add(d);
while (v % d === 0) v /= d;
}
}
if (v > 1) primes.add(v);
}
return primes.size;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets