Distinct Prime Factors of Product of Array

Medium
1316.

Distinct Prime Factors of Product of Array

Distinct Prime Factors of Product of Array is a medium coding problem on arrays, hash table and math, asked in Amazon and TCS interviews.

Given an array of positive integers nums, return the number of distinct prime factors of the product of all its elements.

A prime factor of x is a prime number that divides x. The product itself can be astronomically large — you never need to compute it.

Example 1

Input
nums = [6,10,15]
Output
3
Explanation
The product 900 = 2² · 3² · 5² has the prime factors 2, 3 and 5.

Example 2

Input
nums = [16,32,8]
Output
1
Explanation
Every element is a power of 2.

Example 3

Input
nums = [7,11,77,49]
Output
2

Constraints

  • 1 <= nums.length <= 10^4
  • 2 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var distinctPrimeFactors = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Distinct Prime Factors of Product of Array — Solution

Distinct Prime Factors of Product of Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Distinct Prime Factors of Product of Array is a medium coding problem on arrays, hash table and math, asked in Amazon and TCS interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Math, Number Theory
  • Asked at: Amazon, TCS
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array of positive integers nums, return the number of distinct prime factors of the product of all its elements.

A prime factor of x is a prime number that divides x. The product itself can be astronomically large — you never need to compute it.

Example 1

Input: nums = [6,10,15]
Output: 3
Explanation: The product 900 = 2² · 3² · 5² has the prime factors 2, 3 and 5.

Example 2

Input: nums = [16,32,8]
Output: 1
Explanation: Every element is a power of 2.

Example 3

Input: nums = [7,11,77,49]
Output: 2

Constraints

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

Hints for Distinct Prime Factors of Product of Array

  1. Hint 1

    A prime divides a product exactly when it divides at least one of the factors.

  2. Hint 2

    So the answer is the number of distinct primes that divide at least one element.

  3. Hint 3

    Factor each element by trial division up to its square root and collect the primes in a set.

How to solve Distinct Prime Factors of Product of Array

A prime divides the product if and only if it divides one of the elements (Euclid's lemma), so collect the prime factors of every element in a set.

Approach

  1. For each element v, try divisors d = 2, 3, … while d·d <= v.
  2. When d divides v, record d and divide it out completely.
  3. If v > 1 remains afterwards, it is a prime factor too; record it.
  4. Return the number of distinct primes recorded.

Why it works

Euclid's lemma says a prime dividing a·b divides a or b, so the primes of the product are exactly the union of the elements' primes. In trial division, dividing each found factor out completely guarantees every later divisor that succeeds is prime, and whatever is left above 1 after d·d > v has no divisor up to its square root, so it is prime.

Complexity

  • Time — O(n · √V) with V = 1000
  • Space — O(number of primes ≤ V)

Pitfalls

  • Never multiply the elements together — 10^4 numbers up to 1000 overflow anything.
  • Do not forget the leftover factor greater than √v (for example 997, or the 7 in 14).
  • Count primes, not prime powers: 8 contributes only 2.

Reference solution

Python

from typing import List

def distinctPrimeFactors(nums: List[int]) -> int:
    primes = set()
    for x in nums:
        v = x
        d = 2
        while d * d <= v:
            if v % d == 0:
                primes.add(d)
                while v % d == 0:
                    v //= d
            d += 1
        if v > 1:
            primes.add(v)
    return len(primes)

Java

public static int distinctPrimeFactors(int[] nums) {
    boolean[] seen = new boolean[1001];
    int count = 0;
    for (int x : nums) {
        int v = x;
        for (int d = 2; d * d <= v; d++) {
            if (v % d == 0) {
                if (!seen[d]) { seen[d] = true; count++; }
                while (v % d == 0) v /= d;
            }
        }
        if (v > 1 && !seen[v]) { seen[v] = true; count++; }
    }
    return count;
}

C++

int distinctPrimeFactors(vector<int>& nums) {
    set<int> primes;
    for (int x : nums) {
        int v = x;
        for (int d = 2; d * d <= v; d++) {
            if (v % d == 0) {
                primes.insert(d);
                while (v % d == 0) v /= d;
            }
        }
        if (v > 1) primes.insert(v);
    }
    return primes.size();
}

JavaScript

var distinctPrimeFactors = function(nums) {
    var primes = new Set();
    for (var i = 0; i < nums.length; i++) {
        var v = nums[i];
        for (var d = 2; d * d <= v; d++) {
            if (v % d === 0) {
                primes.add(d);
                while (v % d === 0) v /= d;
            }
        }
        if (v > 1) primes.add(v);
    }
    return primes.size;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets