Distinct Prime Factors Of Product Of Array - Leetcode Solution

Problem statement: Given an array nums of positive integers, return the number of tuples (i, j, k) such that i < j < k and nums[i] * nums[j] * nums[k] contains exactly three distinct prime factors.

Solution: The first step is to find all the prime factors of each element of the array. This could be done using a sieve algorithm. We can maintain an array of prime numbers and mark the multiples of each prime number as composite. In the end, we will have an array of all prime numbers up to a certain limit.

Then, we can iterate through the array and find all the prime factors of each element. We can use a set to store the distinct prime factors of each element.

Now, we need to find all the tuples (i, j, k) such that i < j < k and nums[i] * nums[j] * nums[k] contains exactly three distinct prime factors. We can use a nested loop to iterate through all possible pairs of elements and check if their product, when multiplied by any other element, contains exactly three distinct prime factors.

The time complexity of this algorithm is O(n^3), where n is the length of the array. However, we can optimize it by using a hash map to store the count of elements with the same set of prime factors. This will reduce the time complexity to O(n^2).

Code:

def sieve(limit):
    primes = [True] * (limit+1)
    primes[0] = primes[1] = False
    for i in range(2, int(limit**0.5)+1):
        if primes[i]:
            for j in range(i*i, limit+1, i):
                primes[j] = False
    return [i for i in range(limit+1) if primes[i]]

def distinctPrimeFactors(num, primes):
    factors = set()
    for p in primes:
        while num % p == 0:
            factors.add(p)
            num //= p
        if num == 1:
            break
    return factors

def numTuples(nums):
    primes = sieve(100)
    count = {}
    res = 0
    for i in range(len(nums)):
        factors_i = distinctPrimeFactors(nums[i], primes)
        for j in range(i+1, len(nums)):
            factors_j = distinctPrimeFactors(nums[j], primes)
            for k in range(j+1, len(nums)):
                factors_k = distinctPrimeFactors(nums[k], primes)
                factors = factors_i | factors_j | factors_k
                if len(factors) == 3:
                    key = tuple(sorted(factors))
                    count[key] = count.get(key, 0) + 1
                    res += count[key]
    return res

Explanation of the code:

• The function sieve(limit) is used to generate a list of all prime numbers up to the limit. It uses the sieve of Eratosthenes algorithm.
• The function distinctPrimeFactors(num, primes) takes a number and a list of primes, and returns the set of distinct prime factors of the number.
• The function numTuples(nums) takes an array of integers and returns the number of tuples that satisfy the given condition.
• Inside the function numTuples(nums), we first initialize a dictionary count to store the count of tuples with the same set of prime factors.
• We then iterate through all possible tuples of three elements using a nested loop, and compute their set of prime factors.
• If the set of prime factors contains exactly three elements, we add the tuple to the count and increment the result by the count of tuples with the same set of prime factors.
• In the end, we return the result.

1