Teaching Kids Programming – Distinct Prime Factors of Product of Array

Teaching Kids Programming: Videos on Data Structures and 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 = 25 * 32 * 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 = 210.
There is 1 distinct prime factor so we return 1.

Constraints:
1 <= nums.length <= 10^4
2 <= nums[i] <= 1000

Distinct Prime Factors of Product of Array

This is a problem that requires us to find the number of distinct prime factors for a list of integers. We will be discussing a Python solution to this problem. The solution makes use of sets and loops to iterate through the list of integers and find the distinct prime factors.

The Problem

Before we dive into the solution, let’s first understand the problem statement. Given a list of integers, we need to find the number of distinct prime factors for each integer in the list. For example, consider the following list of integers:

[4, 6, 8, 9, 12]

The distinct prime factors for each integer in the list are as follows:

4: 2
6: 2, 3
8: 2
9: 3
12: 2, 3

Thus, the number of distinct prime factors for the given list of integers is 3.

The Solution

The solution to this problem makes use of sets to store the distinct prime factors. We loop through each integer in the given list and find its prime factors. We add these prime factors to the set of distinct prime factors. Finally, we return the length of the set, which gives us the number of distinct prime factors for the entire list of integers.

Let’s look at the code to understand this solution in more detail.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def distinctPrimeFactors(self, nums: List[int]) -> int:
        a = set()
        for x in nums:
            j = 2
            while x != 1:
                while x % j == 0:
                    x //= j
                    a.add(j)
                j += 1
        return len(a)

class Solution:
    def distinctPrimeFactors(self, nums: List[int]) -> int:
        a = set()
        for x in nums:
            j = 2
            while x != 1:
                while x % j == 0:
                    x //= j
                    a.add(j)
                j += 1
        return len(a)

The function distinctPrimeFactors takes a list of integers nums as input and returns an integer. We initialize an empty set a to store the distinct prime factors. We then loop through each integer x in the list nums.

Inside the loop, we initialize a variable j to 2, which represents the first prime number. We then start a nested loop that divides x by j as long as j is a factor of x. If j is a factor of x, we add it to the set a. We then increment j by 1 (or we can improve to jump to the next Prime number) to check for the next prime factor of x. We continue this process until x is reduced to 1.

Once we have found all the prime factors of x, we move on to the next integer in the list nums and repeat the process. Finally, we return the length of the set a, which gives us the number of distinct prime factors for the entire list of integers.

The time complexity of the given solution is O(NloglogM), where N is the length of the input list and M is the maximum value in the list. This is because we loop through each integer in the input list and for each integer, we find its prime factors using a nested loop that runs until the integer is reduced to 1. The inner loop has a time complexity of O(loglogM) since we are only dividing the number by prime numbers, and there are at most loglogM prime numbers less than or equal to M. Therefore, the overall time complexity of the solution is O(NloglogM).

The space complexity of the solution is also O(NlogM), where N is the length of the input list and M is the maximum value in the list. This is because we are storing the distinct prime factors in a set. The worst-case scenario is when all the integers in the input list are prime, and we need to store all of their prime factors in the set. Since the maximum number of prime factors a number can have is logM, the size of the set will be at most NlogM. Therefore, the space complexity of the solution is O(NlogM).

Conclusion

In this blog post, we have discussed a Python solution to count the number of the distinct prime factors for the product of a given integer array. The solution makes use of sets and loops to find the number of distinct prime factors for a given list of integers. This problem is a good exercise to practice working with loops, sets, and prime numbers.

–EOF (The Ultimate Computing & Technology Blog) —