2521. Distinct Prime Factors of Product of Array
Problem Description
Given an array nums
composed of positive integers, we are asked to determine the count of distinct prime factors present in the product formed by multiplying all the elements in nums
. It's important to remember that a prime number is a number greater than 1 that has no divisors other than 1 and itself. Additionally, a prime factor of a number is a prime number that divides it without leaving a remainder. The task is to ensure we find each unique prime factor once, regardless of how many times it might divide different numbers in the array.
Intuition
The intuition behind the solution is to identify all prime factors for each number in the nums
array and then collect these factors without duplicates to determine their total count.
Here's how we can approach the problem:
- Initialize an empty set that will be used to store unique prime factors.
- Loop through each number in the
nums
array. - For each number, find all prime factors by checking for divisibility from 2 onwards:
- Start from 2 (the smallest prime) and try to divide the number.
- If divisible, it's a prime factor, and we add it to the set.
- Divide the number by this factor repeatedly until it's no longer divisible by this factor.
- Increment the factor and repeat the process until the square of the factor is larger than the number.
- If the remaining number is greater than 1, it means the number itself is a prime and should be included in the set of prime factors.
- Finally, the distinct count of prime factors equals the size of the set holding these factors.
The brilliance of this approach lies in the fact that once a number in nums
is divisible by a prime factor and we divide it out completely, the reduced number cannot be divisible by any previously checked factors. This means we do not have to worry about non-prime numbers during the factorization since they would've already been checked as multiples of the primes. Thus, the remaining number after this process is either 1 or a prime number.
Learn more about Math patterns.
Solution Approach
The implementation of the solution follows these steps:
-
Initialize a set named
s
which will be used to store distinct prime factors encountered across all numbers innums
. A set is chosen because it inherently prevents duplicate entries, ensuring that each prime factor is only counted once, regardless of how many times it divides numbers in the array. -
Iterate through each number
n
innums
. -
For the current number
n
, we initiate a loop to find its prime factors starting fromi = 2
(the smallest prime). The use ofwhile i <= n // i
as the loop condition is a key optimization that reduces the range we need to check. Since ifi
is greater than the square root ofn
,i
cannot be a factor ofn
. -
Inside the loop, we check if
n
is divisible byi
:- If it is,
i
is a prime factor ofn
. We addi
to the sets
. - Then, we use a nested
while
loop to dividen
byi
repeatedly untiln
is no longer divisible byi
. This step ensures that we eliminate all powers ofi
inn
.
- If it is,
-
After exiting the inner
while
loop, we incrementi
by 1 to check the next potential prime factor. -
Once the outer
while
loop completes, there may be a case wheren
(the reduced number) is greater than 1. This remaindern
must be a prime number itself since all its other prime factors have already been divided out. So, we addn
to the sets
. -
After the for-loop completes, all prime factors of all numbers in
nums
have been collected in the sets
. We return the size of the sets
, which gives us the count of distinct prime factors.
This solution approach leans heavily on the fact that every composite number has at least one prime factor less than or equal to its square root, allowing us to search only until n // i
instead of n
. This is a fundamental property of prime numbers and plays a crucial role in the efficiency of the algorithm. Additionally, the solution enforces the uniqueness of prime factors by using a set, and only adds factors to this set, ensuring each factor is only counted once no matter how many numbers it divides in the input array nums
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a simple example. Assume our nums
array is [12, 15]
.
-
We initialize the set
s
to store distinct prime factors encountered across all numbers innums
. Initially,s = {}
. -
We begin iterating through each number in
nums
. The first numbern
is12
. -
We start finding prime factors of
n = 12
beginning withi = 2
.- We find that
12
is divisible by2
, so we add2
to sets
. Now,s = {2}
. - We keep dividing
12
by2
to eliminate all powers of2
inn
. After this process,n
becomes3
(12 divided by 2 twice). - We increment
i
to3
and find that3
is divisible. So we add3
to sets
. Now,s = {2, 3}
. n
is now1
, so we are done with the prime factorization of12
.
- We find that
-
We move to the next number in
nums
which is15
. -
We start finding prime factors of
n = 15
starting withi = 2
.15
is not divisible by2
, so we incrementi
to3
.- We find
15
is divisible by3
, and since3
is already in sets
, we do not need to add it again. We divide15
by3
to remove all factors of3
, andn
becomes5
. - We increment
i
to4
, but since4
is not prime, we go to5
. 5
dividesn
(now5
), and we add5
to the sets
since it is not already there. Now,s = {2, 3, 5}
.n
is now1
, so we have completed the prime factorization for15
.
-
All numbers in
nums
have been processed. The sets
now contains all the distinct prime factors{2, 3, 5}
. -
The size of the set
s
represents the count of distinct prime factors. There are3
distinct prime factors in the product of all numbers innums
.
Therefore, the answer is 3
āthere are three distinct prime factors in the product of all numbers in the given nums
array [12, 15]
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def distinctPrimeFactors(self, nums: List[int]) -> int:
5 # Initialize an empty set to hold unique prime factors
6 prime_factors_set = set()
7
8 # Iterate over all the numbers in the list
9 for number in nums:
10 factor = 2 # Start checking for prime factors from the smallest prime
11
12 # Use trial division to find prime factors of the number
13 while factor <= number // factor:
14 # If the factor divides the number, it is a prime factor
15 if number % factor == 0:
16 prime_factors_set.add(factor)
17 # Divide the number by the prime factor until it is no longer divisible
18 while number % factor == 0:
19 number //= factor
20 # Increment the factor by 1 to check the next possible prime factor
21 factor += 1
22
23 # If the remaining number is greater than 1, it is a prime factor itself
24 if number > 1:
25 prime_factors_set.add(number)
26
27 # The result is the count of unique prime factors found in all numbers
28 return len(prime_factors_set)
29
1class Solution {
2
3 // Function to count the number of distinct prime factors among all numbers in the array
4 public int distinctPrimeFactors(int[] nums) {
5 // Initialize a set to store unique prime factors
6 Set<Integer> uniquePrimeFactors = new HashSet<>();
7
8 // Iterate over each number in the array
9 for (int number : nums) {
10 // Check for factors starting from 2 up to the square root of the number
11 for (int factor = 2; factor <= number / factor; ++factor) {
12 // If 'factor' is a divisor of 'number'
13 if (number % factor == 0) {
14 // Add 'factor' to the set of unique prime factors
15 uniquePrimeFactors.add(factor);
16 // Remove all occurrences of this prime factor from 'number'
17 while (number % factor == 0) {
18 number /= factor;
19 }
20 }
21 }
22 // If the remaining 'number' is a prime number greater than 1, add it to the set
23 if (number > 1) {
24 uniquePrimeFactors.add(number);
25 }
26 }
27
28 // Return the size of the set, i.e., the number of distinct prime factors
29 return uniquePrimeFactors.size();
30 }
31}
32
1#include <vector>
2#include <unordered_set>
3using namespace std;
4
5class Solution {
6public:
7 // Function to calculate the number of distinct prime factors from an array of numbers.
8 int distinctPrimeFactors(vector<int>& nums) {
9 unordered_set<int> uniquePrimes; // Set to store unique prime factors.
10
11 // Iterate through each number in the array.
12 for (int& num : nums) {
13 // Check for factors starting from 2 to the square root of the number.
14 for (int i = 2; i <= num / i; ++i) {
15 // If 'i' is a divisor of 'num', it could be a prime factor.
16 if (num % i == 0) {
17 uniquePrimes.insert(i); // Insert the prime factor into the set.
18 // Divide 'num' by 'i' completely.
19 while (num % i == 0) {
20 num /= i;
21 }
22 }
23 }
24 // If 'num' is still greater than 1, then it is a prime number itself.
25 if (num > 1) {
26 uniquePrimes.insert(num); // Insert the remaining prime factor into the set.
27 }
28 }
29
30 // Return the number of distinct prime factors found.
31 return uniquePrimes.size();
32 }
33};
34
1// Importing necessary types for Set.
2import { Set } from 'typescript-collections';
3
4// Function to calculate the number of distinct prime factors from an array of numbers.
5function distinctPrimeFactors(nums: Array<number>): number {
6 let uniquePrimes: Set<number> = new Set<number>(); // Set to store unique prime factors.
7
8 // Iterate through each number in the array.
9 for (let num of nums) {
10 // Check for factors starting from 2 to the square root of the number.
11 for (let i = 2; i * i <= num; i++) {
12 // If 'i' is a divisor of 'num', it could be a prime factor.
13 if (num % i === 0) {
14 uniquePrimes.add(i); // Insert the prime factor into the set.
15 // Divide 'num' by 'i' completely.
16 while (num % i === 0) {
17 num /= i;
18 }
19 }
20 }
21 // If 'num' is still greater than 1, then it is a prime number itself.
22 if (num > 1) {
23 uniquePrimes.add(num); // Insert the remaining prime factor into the set.
24 }
25 }
26
27 // Return the number of distinct prime factors found.
28 return uniquePrimes.size();
29}
30
31// Note: TypeScript does not have a Set type with a size() method in the standard library.
32// The `typescript-collections` package is a third-party library that could be used here.
33// If you want to stay with the standard Set from TypeScript, modify the return line to:
34// return uniquePrimes.size;
35
Time and Space Complexity
The time complexity of the given code is determined by the nested loop where we are finding the distinct prime factors for each number in the input list nums
. The outer loop iterates over each number in the list. The inner while loop checks for factors starting from 2
up to sqrt(n)
(since i <= n // i
is equivalent to i * i <= n
). Factoring a number takes at most O(sqrt(n))
where n
is the number being factored. Hence, if the largest number in the list is N
, the time complexity of factoring all numbers is O(M * sqrt(N))
, where M
is the length of the list nums
.
The space complexity of the code is determined by the set s
which stores the distinct prime factors of all the numbers in the list. In the worst-case scenario, this could store all primes less than or equal to N
(the largest number in the list). The number of primes less than N
is approximately N / log(N)
by the prime number theorem. Consequently, the space complexity is O(N / log(N))
.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!