Distinct Prime Factors of Product of Array

Distinct Prime Factors of Product of Array

What is this problem about?

The Distinct Prime Factors of Product of Array interview question provides an array of integers and asks you to find the number of unique prime factors that would exist if you were to multiply all elements of the array together. You don't actually need to perform the multiplication (which would result in a massive overflow); you only need to identify the prime building blocks of the individual numbers.

Why is this asked in interviews?

Companies like Microsoft and Google use this to test your knowledge of Number Theory interview patterns. It evaluations whether you can break down numbers into their prime components and your understanding of prime factorization. It also tests your ability to use a Hash Set to collect unique values across multiple operations efficiently.

Algorithmic pattern used

This problem uses Prime Factorization and a Hash Set.

1. Iterate through each number in the array.
2. For each number, find its prime factors. You do this by checking divisibility starting from 2 up to $\sqrt{num}$.
3. Add every prime factor found to a global HashSet.
4. The size of the HashSet at the end is the number of distinct prime factors.

Example explanation

Array: [2, 4, 3, 7, 10, 6]

1. 2: Factor {2}.
2. 4: Factors {2, 2}. Only 2 is prime.
3. 3: Factor {3}.
4. 7: Factor {7}.
5. 10: Factors {2, 5}.
6. 6: Factors {2, 3}. Set: {2, 3, 5, 7}. Count: 4.

Common mistakes candidates make

• Actual Multiplication: Trying to multiply the numbers first, which is impossible due to the astronomical size of the product.
• Inefficient Factorization: Not stopping at $\sqrt{num}$ during factorization, leading to $O(N)$ instead of $O(\sqrt{N})$ per number.
• Including 1: Forgetting that 1 is not a prime number.
• Non-prime factors: Adding composite numbers (like 4 or 6) to the set instead of their prime components.

Interview preparation tip

Understand the standard prime factorization algorithm: divide by 2 while possible, then check odd numbers up to $\sqrt{N}$. If $N > 1$ after the loop, the remaining $N$ is also prime. This is a foundational Math interview pattern that appears in many GCD, LCM, and factor-related problems.