We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Distinct Prime Factors of Product of Array

Number: 2609

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an array of positive integers, determine the number of distinct prime factors in the product of all the elements in the array. Instead of computing the actual product (which can be huge), you should identify the prime factors for each element and count the unique ones.

Key Insights

  • Instead of multiplying all numbers (which can lead to overflow), factorize each number separately.
  • Use trial division (up to the square root of the number) to find prime factors, as the maximum value is small (up to 1000).
  • Store discovered prime factors in a set to automatically handle duplicates.
  • The final answer is the size of the set containing all distinct prime factors.

Space and Time Complexity

Time Complexity: O(n * sqrt(m)) per number where m is the maximum value in the array (m ≤ 1000). With n up to 10^4 and sqrt(1000) ≈ 31, the solution is efficient. Space Complexity: O(P) where P is the number of distinct primes encountered (relatively small, bounded by the primes up to 1000).

Solution

The solution involves iterating over each number in the input array and performing prime factorization using trial division. For each number, check divisibility starting from 2 up to the square root of the number. If a divisor is found, add it to a set and divide out all occurrences of that divisor. If after processing all divisors the remaining number is greater than 1, it is prime and is added to the set. Finally, return the size of the set, which represents the number of distinct prime factors in the underlying product.

Code Solutions

# Function to compute prime factors of a number using trial division
def get_prime_factors(num):
    factors = set()                      # to store unique prime factors
    # Check for factor 2 separately for efficiency
    while num % 2 == 0:
        factors.add(2)
        num //= 2
    # Check for odd factors starting from 3 up to sqrt(num)
    factor = 3
    while factor * factor <= num:
        while num % factor == 0:
            factors.add(factor)
            num //= factor
        factor += 2
    # If the remaining num is greater than 1, it is a prime factor
    if num > 1:
        factors.add(num)
    return factors

def distinctPrimeFactors(nums):
    all_factors = set()                  # overall distinct prime factors for product
    for num in nums:
        factors = get_prime_factors(num) # get factors for the current number
        all_factors.update(factors)      # merge with overall set
    return len(all_factors)              # number of distinct primes

# Example usage:
nums = [2, 4, 3, 7, 10, 6]
print(distinctPrimeFactors(nums))  # Output: 4
← Back to All Questions