Scale Engineer

Distinct Prime Factors of Product of Array

Med
#2301Time: O(N * sqrt(M)), where N is the number of elements in `nums` and M is the maximum value of an element in `nums`. For each of the N numbers, we perform trial division up to `sqrt(M)`.Space: O(P_M), where P_M is the number of prime numbers less than or equal to M (the maximum value in `nums`). This space is used by the `HashSet`. Since M <= 1000, the number of primes is a small constant (168), so the space can be considered O(1).
Patterns
MathNumber Theory
Data structures
ArrayHash Table

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through each number in the input array nums. For each number, it finds all its prime factors using trial division. A HashSet is used to store the distinct prime factors found across all numbers. The final answer is the size of this set.

Algorithm

  • Initialize an empty HashSet<Integer> named distinctPrimes.
  • Iterate through each integer num in the input array nums.
  • For each num, find its prime factors:
    • Iterate with a divisor d from 2 up to sqrt(num).
    • If d divides num:
      • Add d to the distinctPrimes set.
      • Continuously divide num by d until it is no longer divisible.
    • After the loop, if num is still greater than 1, it is a prime factor itself. Add it to distinctPrimes.
  • Return the final size of the distinctPrimes set.

Walkthrough

The core idea is that the set of prime factors of the product of several numbers is the union of the sets of prime factors of each individual number. This avoids calculating the potentially huge product which would cause an overflow.

We initialize a HashSet to keep track of the unique prime factors. We then loop through each num in the nums array. For each num, we perform prime factorization by trial division. We start with a divisor d = 2 and check for divisibility. If d divides num, we add d to our HashSet and then divide num by d repeatedly until it's no longer divisible. This ensures we handle powers of a prime factor (like 8 = 2*2*2) correctly. We then increment d and repeat the process. We only need to check divisors up to the square root of the current num. If, after the loop, the remaining value of num is greater than 1, it must be a prime factor itself (e.g., when factorizing 14, after dividing by 2, we are left with 7). We add this remaining number to the set. Finally, the number of distinct prime factors is simply the size of the HashSet.

import java.util.HashSet;import java.util.Set; class Solution {    public int distinctPrimeFactors(int[] nums) {        Set<Integer> primeFactors = new HashSet<>();        for (int num : nums) {            findPrimeFactors(num, primeFactors);        }        return primeFactors.size();    }     private void findPrimeFactors(int n, Set<Integer> factors) {        // Trial division to find prime factors        for (int i = 2; i * i <= n; i++) {            if (n % i == 0) {                factors.add(i);                while (n % i == 0) {                    n /= i;                }            }        }        // If n is a prime number greater than 1 after the loop        if (n > 1) {            factors.add(n);        }    }}

Complexity

Time

O(N * sqrt(M)), where N is the number of elements in `nums` and M is the maximum value of an element in `nums`. For each of the N numbers, we perform trial division up to `sqrt(M)`.

Space

O(P_M), where P_M is the number of prime numbers less than or equal to M (the maximum value in `nums`). This space is used by the `HashSet`. Since M <= 1000, the number of primes is a small constant (168), so the space can be considered O(1).

Trade-offs

Pros

  • Simple to understand and implement.

  • Does not require any pre-computation.

  • Space efficient as it only stores the final prime factors.

Cons

  • Less efficient than approaches using pre-computation, as it repeatedly calculates factors for numbers.

  • The factorization step O(sqrt(M)) is slower than the O(log M) factorization possible with sieves.

Solutions

class Solution { public int distinctPrimeFactors ( int [] nums ) { Set < Integer > s = new HashSet <>(); for ( int n : nums ) { for ( int i = 2 ; i <= n / i ; ++ i ) { if ( n % i == 0 ) { s . add ( i ); while ( n % i == 0 ) { n /= i ; } } } if ( n > 1 ) { s . add ( n ); } } return s . size (); } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem