Jobs

Interviews

Discussions

Distinct Prime Factors of Product of Array

Medium

Asked by:

40 views

Topics:

ArraysGreedy Algorithms

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 = 2⁵ * 3² * 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 = 2¹⁰.
There is 1 distinct prime factor so we return 1.

Constraints:

1 <= nums.length <= 10⁴
2 <= nums[i] <= 1000

Try coding it in LeetCode

Distinct Prime Factors of Product of Array

Medium

Asked by:

40 views

Topics:

ArraysGreedy Algorithms

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 = 2⁵ * 3² * 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 = 2¹⁰.
There is 1 distinct prime factor so we return 1.

Constraints:

1 <= nums.length <= 10⁴
2 <= nums[i] <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value for each number in the input array?
Can the input array contain zero, negative numbers, or non-integer values?
If the product of the array elements is 1 (e.g., an empty array or an array containing only 1s), what should the function return?
Are we looking for a set of distinct prime factors, or is the order of the factors significant?
Are there any memory constraints that I should be aware of, given the potential size of the product?

Brute Force Solution

Approach

The brute force approach to finding distinct prime factors in the product of an array involves first calculating the product of all numbers in the array. Then, it finds all the prime numbers that divide this product.

Here's how the algorithm would work step-by-step:

First, multiply all the numbers in the array together to get one big number.
Next, start with the smallest prime number, which is 2.
Check if 2 divides the big number evenly. If it does, remember that 2 is a prime factor.
Keep dividing the big number by 2 until it no longer divides evenly.
Move on to the next prime number, which is 3.
Check if 3 divides the big number evenly. If it does, remember that 3 is a prime factor.
Keep dividing the big number by 3 until it no longer divides evenly.
Continue this process with the next prime numbers (5, 7, 11, and so on).
Stop when the big number becomes 1 or when the next prime number to check is larger than the square root of the original big number. Any remaining value of the big number greater than 1 at this point is also a prime factor.
Finally, collect all the prime numbers that you remembered as prime factors. These are the distinct prime factors of the product.

Code Implementation

def distinct_prime_factors_brute_force(numbers):
    product_of_numbers = 1
    for number in numbers:
        product_of_numbers *= number

    distinct_prime_factors = set()
    divisor = 2

    # Iterate through potential prime factors
    while divisor * divisor <= product_of_numbers:
        if product_of_numbers % divisor == 0:
            # Divisor is a prime factor
            distinct_prime_factors.add(divisor)

            # Divide out the prime factor until it's no longer a factor
            while product_of_numbers % divisor == 0:
                product_of_numbers //= divisor

        divisor += 1

    # If product_of_numbers > 1, it's also a prime factor
    if product_of_numbers > 1:
        distinct_prime_factors.add(product_of_numbers)

    return len(distinct_prime_factors)

Big(O) Analysis

Time Complexity

O(N + sqrt(P)) – The algorithm first calculates the product P of all N numbers in the input array, which takes O(N) time. Then, it iterates through potential prime factors up to the square root of P. The primality test and division within the loop on the large product P takes O(sqrt(P)) in the worst case. Therefore, the overall time complexity is dominated by O(N + sqrt(P)), where N is the size of the input array and P is the product of the array elements. Since sqrt(P) can be much larger than N, the runtime is essentially O(sqrt(P)) when P is a very large number.

Space Complexity

O(1) – The algorithm primarily uses a few variables to store the current prime number being checked and the potentially modified product. The algorithm remembers distinct prime factors, but the number of such factors is limited by the original product and doesn't scale directly with the input array's size N. The variables consume a constant amount of extra space regardless of the size of the input array. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

Instead of finding prime factors for each number in the array and then removing duplicates, we can optimize by focusing on finding primes for the product of all numbers. This avoids redundant calculations and uses a set to efficiently track distinct prime factors. We only need to consider prime numbers up to the square root of the maximum value within the given array.

Here's how the algorithm would work step-by-step:

Create an empty set to store the unique prime factors we find.
Find the largest number in the input. The largest possible prime factor we might encounter cannot be larger than this largest number.
Go through each number in the input.
For each number, try dividing it by prime numbers starting from 2. If a number is divisible by a prime number, add that prime to our set and divide the original number by the prime until it's no longer divisible.
If after the above division, the number is still greater than 1, then that remaining number itself is a prime factor. Add it to our set.
Finally, the size of our set will give us the total number of distinct prime factors.

Code Implementation

def distinctPrimeFactors(numbers):
    distinct_prime_factors = set()

    largest_number = max(numbers)

    for number in numbers:
        current_number = number

        # Iterate through possible prime factors
        for factor in range(2, int(number**0.5) + 1):
            # Repeatedly divide to eliminate the prime factor
            while current_number % factor == 0:
                distinct_prime_factors.add(factor)
                current_number //= factor

        # If the remaining number is > 1, it's a prime
        if current_number > 1:
            distinct_prime_factors.add(current_number)

    return len(distinct_prime_factors)

Big(O) Analysis

Time Complexity

O(n * sqrt(M)) – Let n be the number of elements in the input array, and M be the maximum value among those elements. The outer loop iterates through each number in the input array, which takes O(n) time. Inside this loop, we perform prime factorization. The worst-case time complexity for prime factorization of a number x is O(sqrt(x)). Since x can be at most M, the prime factorization within the inner while loop takes O(sqrt(M)) time. Therefore, the overall time complexity is O(n * sqrt(M)).

Space Complexity

O(sqrt(M)) – The algorithm uses a set to store distinct prime factors. In the worst case, the largest number in the input array, let's call it M, could have prime factors up to its square root. Therefore, the size of the set can grow up to the number of primes less than or equal to the square root of M. The space used by the set is thus proportional to the number of such primes which is approximately O(sqrt(M) / log(sqrt(M))), but in big O notation it is simplified to O(sqrt(M)).

Edge Cases

Case	How to Handle
Empty or null input array	Return an empty set immediately, as there are no numbers to factorize.
Array contains zero	Zero multiplied with any other number results in zero, so the final product will be zero which has no prime factors, thus return empty set.
Array contains one	One does not contribute any prime factors, so it can be ignored in factorization.
Array contains negative numbers	Take the absolute value of the product, since the sign does not affect prime factors.
Array with extremely large numbers causing integer overflow	Use a language with support for arbitrary precision arithmetic or consider breaking the problem down into smaller chunks to avoid integer overflow.
Array with large number of elements consisting of small primes.	Optimize the prime factorization algorithm to efficiently handle repeated small prime factors.
Array containing duplicate numbers	Duplicates can be handled by accounting for the count during multiplication and prime factorization; only unique prime factors are added to the set.
Resulting product has no prime factors (product is 1)	After processing the entire array, return an empty set if no prime factors were found (product is 1).

Empty or null input array

How to Handle:

Return an empty set immediately, as there are no numbers to factorize.

Array contains zero

How to Handle:

Zero multiplied with any other number results in zero, so the final product will be zero which has no prime factors, thus return empty set.

Array contains one

How to Handle:

One does not contribute any prime factors, so it can be ignored in factorization.

Array contains negative numbers

How to Handle:

Take the absolute value of the product, since the sign does not affect prime factors.

Array with extremely large numbers causing integer overflow

How to Handle:

Use a language with support for arbitrary precision arithmetic or consider breaking the problem down into smaller chunks to avoid integer overflow.

Array with large number of elements consisting of small primes.

How to Handle:

Optimize the prime factorization algorithm to efficiently handle repeated small prime factors.

Array containing duplicate numbers

How to Handle:

Duplicates can be handled by accounting for the count during multiplication and prime factorization; only unique prime factors are added to the set.

Resulting product has no prime factors (product is 1)

How to Handle:

After processing the entire array, return an empty set if no prime factors were found (product is 1).

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value for each number in the input array?
Can the input array contain zero, negative numbers, or non-integer values?
If the product of the array elements is 1 (e.g., an empty array or an array containing only 1s), what should the function return?
Are we looking for a set of distinct prime factors, or is the order of the factors significant?
Are there any memory constraints that I should be aware of, given the potential size of the product?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, multiply all the numbers in the array together to get one big number.
Next, start with the smallest prime number, which is 2.
Check if 2 divides the big number evenly. If it does, remember that 2 is a prime factor.
Keep dividing the big number by 2 until it no longer divides evenly.
Move on to the next prime number, which is 3.
Check if 3 divides the big number evenly. If it does, remember that 3 is a prime factor.
Keep dividing the big number by 3 until it no longer divides evenly.
Continue this process with the next prime numbers (5, 7, 11, and so on).
Stop when the big number becomes 1 or when the next prime number to check is larger than the square root of the original big number. Any remaining value of the big number greater than 1 at this point is also a prime factor.
Finally, collect all the prime numbers that you remembered as prime factors. These are the distinct prime factors of the product.

Code Implementation

def distinct_prime_factors_brute_force(numbers):
    product_of_numbers = 1
    for number in numbers:
        product_of_numbers *= number

    distinct_prime_factors = set()
    divisor = 2

    # Iterate through potential prime factors
    while divisor * divisor <= product_of_numbers:
        if product_of_numbers % divisor == 0:
            # Divisor is a prime factor
            distinct_prime_factors.add(divisor)

            # Divide out the prime factor until it's no longer a factor
            while product_of_numbers % divisor == 0:
                product_of_numbers //= divisor

        divisor += 1

    # If product_of_numbers > 1, it's also a prime factor
    if product_of_numbers > 1:
        distinct_prime_factors.add(product_of_numbers)

    return len(distinct_prime_factors)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Create an empty set to store the unique prime factors we find.
Find the largest number in the input. The largest possible prime factor we might encounter cannot be larger than this largest number.
Go through each number in the input.
For each number, try dividing it by prime numbers starting from 2. If a number is divisible by a prime number, add that prime to our set and divide the original number by the prime until it's no longer divisible.
If after the above division, the number is still greater than 1, then that remaining number itself is a prime factor. Add it to our set.
Finally, the size of our set will give us the total number of distinct prime factors.

Code Implementation

def distinctPrimeFactors(numbers):
    distinct_prime_factors = set()

    largest_number = max(numbers)

    for number in numbers:
        current_number = number

        # Iterate through possible prime factors
        for factor in range(2, int(number**0.5) + 1):
            # Repeatedly divide to eliminate the prime factor
            while current_number % factor == 0:
                distinct_prime_factors.add(factor)
                current_number //= factor

        # If the remaining number is > 1, it's a prime
        if current_number > 1:
            distinct_prime_factors.add(current_number)

    return len(distinct_prime_factors)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return an empty set immediately, as there are no numbers to factorize.
Array contains zero	Zero multiplied with any other number results in zero, so the final product will be zero which has no prime factors, thus return empty set.
Array contains one	One does not contribute any prime factors, so it can be ignored in factorization.
Array contains negative numbers	Take the absolute value of the product, since the sign does not affect prime factors.
Array with extremely large numbers causing integer overflow	Use a language with support for arbitrary precision arithmetic or consider breaking the problem down into smaller chunks to avoid integer overflow.
Array with large number of elements consisting of small primes.	Optimize the prime factorization algorithm to efficiently handle repeated small prime factors.
Array containing duplicate numbers	Duplicates can be handled by accounting for the count during multiplication and prime factorization; only unique prime factors are added to the set.
Resulting product has no prime factors (product is 1)	After processing the entire array, return an empty set if no prime factors were found (product is 1).

Empty or null input array

How to Handle:

Return an empty set immediately, as there are no numbers to factorize.

Array contains zero

How to Handle:

Zero multiplied with any other number results in zero, so the final product will be zero which has no prime factors, thus return empty set.

Array contains one

How to Handle:

One does not contribute any prime factors, so it can be ignored in factorization.

Array contains negative numbers

How to Handle:

Take the absolute value of the product, since the sign does not affect prime factors.

Array with extremely large numbers causing integer overflow

How to Handle:

Use a language with support for arbitrary precision arithmetic or consider breaking the problem down into smaller chunks to avoid integer overflow.

Array with large number of elements consisting of small primes.

How to Handle:

Optimize the prime factorization algorithm to efficiently handle repeated small prime factors.

Array containing duplicate numbers

How to Handle:

Duplicates can be handled by accounting for the count during multiplication and prime factorization; only unique prime factors are added to the set.

Resulting product has no prime factors (product is 1)

How to Handle:

After processing the entire array, return an empty set if no prime factors were found (product is 1).