2521. Distinct Prime Factors of Product of Array LeetCode Solution

In this guide, you will get 2521. Distinct Prime Factors of Product of Array LeetCode Solution with the best time and space complexity. The solution to Distinct Prime Factors of Product of Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Distinct Prime Factors of Product of Array solution in C++
  4. Distinct Prime Factors of Product of Array solution in Java
  5. Distinct Prime Factors of Product of Array solution in Python
  6. Additional Resources
2521. Distinct Prime Factors of Product of Array LeetCode Solution image

Problem Statement of Distinct Prime Factors of Product of Array

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 <= 104
2 <= nums[i] <= 1000

Complexity Analysis

  • Time Complexity: O(n\log^2 n)
  • Space Complexity: O(n)
See also  2000. Reverse Prefix of Word LeetCode Solution

2521. Distinct Prime Factors of Product of Array LeetCode Solution in C++

class Solution {
 public:
  int distinctPrimeFactors(vector<int>& nums) {
    unordered_set<int> primes;

    for (const int num : nums)
      addPrimeFactors(primes, num);

    return primes.size();
  }

 private:
  void addPrimeFactors(unordered_set<int>& primes, int num) {
    for (int divisor = 2; divisor <= num; ++divisor)
      if (num % divisor == 0) {
        primes.insert(divisor);
        while (num % divisor == 0)
          num /= divisor;
      }
  }
};
/* code provided by PROGIEZ */

2521. Distinct Prime Factors of Product of Array LeetCode Solution in Java

class Solution {
  public int distinctPrimeFactors(int[] nums) {
    Set<Integer> primes = new HashSet<>();

    for (final int num : nums)
      addPrimeFactors(primes, num);

    return primes.size();
  }

  private void addPrimeFactors(Set<Integer> primes, int num) {
    for (int divisor = 2; divisor <= num; ++divisor)
      if (num % divisor == 0) {
        primes.add(divisor);
        while (num % divisor == 0)
          num /= divisor;
      }
  }
}
// code provided by PROGIEZ

2521. Distinct Prime Factors of Product of Array LeetCode Solution in Python

class Solution:
  def distinctPrimeFactors(self, nums: list[int]) -> int:
    primes = set()

    for num in nums:
      self._addPrimeFactors(primes, num)

    return len(primes)

  def _addPrimeFactors(self, primes: set[int], num: int) -> None:
    for divisor in range(2, num + 1):
      if num % divisor == 0:
        primes.add(divisor)
        while num % divisor == 0:
          num //= divisor
# code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.