## Similar Problems

Similar Problems not available

# Distinct Prime Factors Of Product Of Array - Leetcode Solution

## Companies:

LeetCode: Distinct Prime Factors Of Product Of Array Leetcode Solution

Difficulty: Medium

Topics: math hash-table array

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.

## Distinct Prime Factors Of Product Of Array Solution Code

`1`