LeetCode 2521 - Distinct Prime Factors of Product of Array

The problem asks us to compute the number of distinct prime factors in the product of an array of positive integers, nums.

leetcodemediumarrayhash-tablemathnumber-theory

LeetCode Problem 2521

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Number Theory

Solution

Problem Understanding

The problem asks us to compute the number of distinct prime factors in the product of an array of positive integers, nums. In simpler terms, we are given a list of numbers, and we want to know how many unique prime numbers appear if we were to multiply all the numbers together and factorize the resulting product.

The input nums is an array of integers, where each integer is at least 2 and at most 1000, and the array can have up to 10,000 elements. This constraint ensures that individual numbers are small, but their product could be extremely large - far too large to compute directly. Therefore, a naive approach that multiplies all numbers and then factorizes the result will fail due to integer overflow or performance limitations.

The expected output is a single integer: the count of unique prime numbers that divide the product of all elements in the array.

Important observations include:

  • Each number is between 2 and 1000, so all prime factors are also ≤ 1000.
  • Repeated primes in different numbers should only be counted once.
  • Multiplying all numbers explicitly is unnecessary and impractical because of overflow.

Edge cases that could challenge a naive solution include:

  1. All numbers are powers of the same prime (e.g., [2,4,8,16]), where the product has only one distinct prime factor.
  2. Numbers are distinct primes themselves.
  3. Numbers with overlapping prime factors (e.g., [6,10,15]).

Approaches

The brute-force approach is to first multiply all numbers in nums to form the product, then factorize the product to count distinct prime factors. This is correct mathematically but impractical due to the enormous size of the product for large arrays. It also requires high-precision arithmetic to avoid overflow.

The optimal approach leverages the key observation that all numbers are ≤ 1000. We can precompute all prime numbers up to 1000 using the Sieve of Eratosthenes. Then, for each number in nums, we factorize it directly and insert its prime factors into a set to track unique primes. This avoids multiplying the numbers and keeps the operation efficient, since each number is small and factorization is fast.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(1) Multiply all numbers (m = number of bits in product) then factorize, impractical due to overflow
Optimal O(n * √maxNum) O(p) Factorize each number directly using primes up to maxNum (≤1000), store in set (p = number of distinct primes ≤1000)

Algorithm Walkthrough

  1. Generate all prime numbers up to 1000 using the Sieve of Eratosthenes. This allows efficient factorization for numbers in nums.
  2. Initialize an empty set, distinct_primes, to store unique prime factors.
  3. Iterate through each number num in nums.
  4. For each num, iterate through the list of primes:
  • If the prime divides num, add it to distinct_primes.
  • Continue dividing num by the prime until it is no longer divisible.
  • Stop checking further primes if num becomes 1.
  1. After processing all numbers, return the size of distinct_primes.

Why it works: Each prime factor from each number is inserted exactly once into the set, ensuring uniqueness. Because we factorize each number directly, we avoid the impractical multiplication of large numbers. The sieve guarantees that we consider all possible primes that could appear.

Python Solution

from typing import List

class Solution:
    def distinctPrimeFactors(self, nums: List[int]) -> int:
        def sieve(n: int) -> List[int]:
            is_prime = [True] * (n + 1)
            is_prime[0] = is_prime[1] = False
            for i in range(2, int(n**0.5) + 1):
                if is_prime[i]:
                    for j in range(i*i, n + 1, i):
                        is_prime[j] = False
            return [i for i, val in enumerate(is_prime) if val]
        
        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)

The Python implementation first precomputes all primes up to 1000 using the sieve. Then, for each number in the array, it checks divisibility by each prime and records unique prime factors. If a number itself is a prime larger than the square root of its original value, it is added directly to the set.

Go Solution

func distinctPrimeFactors(nums []int) int {
    sieve := func(n int) []int {
        isPrime := make([]bool, n+1)
        for i := 2; i <= n; i++ {
            isPrime[i] = true
        }
        for i := 2; i*i <= n; i++ {
            if isPrime[i] {
                for j := i * i; j <= n; j += i {
                    isPrime[j] = false
                }
            }
        }
        primes := []int{}
        for i := 2; i <= n; i++ {
            if isPrime[i] {
                primes = append(primes, i)
            }
        }
        return primes
    }

    primes := sieve(1000)
    distinct := make(map[int]struct{})

    for _, num := range nums {
        temp := num
        for _, prime := range primes {
            if prime*prime > temp {
                break
            }
            if temp%prime == 0 {
                distinct[prime] = struct{}{}
                for temp%prime == 0 {
                    temp /= prime
                }
            }
        }
        if temp > 1 {
            distinct[temp] = struct{}{}
        }
    }

    return len(distinct)
}

The Go solution follows the same logic as Python. It uses a map with empty structs to simulate a set for storing distinct primes. The sieve and factorization logic is equivalent, adapted to Go's syntax and types.

Worked Examples

Example 1: nums = [2,4,3,7,10,6]

Step through:

num distinct_primes after processing
2 {2}
4 {2}
3 {2, 3}
7 {2, 3, 7}
10 {2, 3, 5, 7}
6 {2, 3, 5, 7}

Output: 4

Example 2: nums = [2,4,8,16]

Step through:

num distinct_primes after processing
2 {2}
4 {2}
8 {2}
16 {2}

Output: 1

Complexity Analysis

Measure Complexity Explanation
Time O(n * √maxNum) For each number, we iterate through primes up to its square root, n = length of nums, maxNum = 1000
Space O(p) p = number of primes ≤ 1000 stored in sieve and set for distinct factors

The sieve generation is O(maxNum * log log maxNum), negligible compared to n * √maxNum for n up to 10,000.

Test Cases

# Provided examples
assert Solution().distinctPrimeFactors([2,4,3,7,10,6]) == 4  # mixed primes and composites
assert Solution().distinctPrimeFactors([2,4,8,16]) == 1      # powers of same prime

# Additional cases
assert Solution().distinctPrimeFactors([2,3,5,7,11,13]) == 6  # all primes
assert Solution().distinctPrimeFactors([6,10,15]) == 3       # overlapping prime factors
assert Solution().distinctPrimeFactors([997]) == 1           # single large prime
assert Solution().distinctPrimeFactors([1000,1000]) == 3     # large composite 2^3 * 5^3
assert Solution().distinctPrimeFactors([2]*10000) == 1       # repeated prime 2, large n
Test Why
[2,4,3,7,10,6] Mixed numbers with multiple distinct primes
[2,4,8,16] Powers of the same prime, only one distinct factor
[2,3,5,7,11,13] All distinct primes
[6,10,15] Numbers sharing some primes
[997] Single prime edge case
[1000,1000] Large composite numbers
[2]*10000 Large array size with repeated primes

Edge Cases

One important edge case is when all numbers in the array are powers of a single prime. For example, `[2,4,