1390. Four Divisors
Problem Description
The given problem presents us with an integer array nums
. Our task is to find the sum of all divisors of each integer in nums
that exactly have four divisors. To clarify, for an integer to qualify, it must have exactly four distinct divisors - including '1' and itself. If an integer in the array doesn't meet this criteria, it's not included in the sum. If there's no such integer in the array meeting the criteria, then the function should return 0
.
Intuition
To approach this problem, consider that an integer with exactly four divisors can only qualify if it's either a product of two distinct prime numbers or a cube of a prime number (since the cube will have divisors 1, the prime, the square of the prime, and the cube of the prime). Given this premise, our strategy is as follows:
- Iterate through every element of the input array
nums
. - For each element, try to find all its divisors.
- Keep a count of how many divisors we've found and simultaneously calculate their sum.
- If by the end, the count of divisors is exactly 4, add the sum of these divisors to our overall total.
- If it's not 4 divisors, disregard this integer and move to the next one.
- Repeat this process until we've checked all the integers in the array, and return the total sum.
The provided solution code defines a nested function f(x)
that calculates the sum of divisors of an integer x
if it has exactly four divisors. This function uses a while loop to find divisors of x
. For each divisor i
found, the count is incremented and the sum is updated accordingly. Once all potential divisors are checked, the function returns either the sum of divisors, if there are exactly four, or 0
otherwise.
This nested function is then applied to each element in nums
with a generator expression that's passed to the sum
function, rolling up the total sum of qualifying divisors. The concept of generators is efficient here since it avoids the need for an intermediate list to hold values for divisors' sums, thus saving memory.
Learn more about Math patterns.
Solution Approach
The solution implements a brute-force algorithm to find integers with exactly four divisors. Here's the step-by-step approach broken down:
-
A helper function
f(x)
is declared inside theSolution
class, which takes an integerx
as input and returns the sum of its divisors if it has exactly four divisors, otherwise returns0
. -
Inside the function
f(x)
, we initialize two variables:cnt
to count the number of divisors (starting with 2, to account for '1' andx
itself), ands
to keep the sum of divisors (initialized tox + 1
for the same reason). -
A while loop is used to iterate over possible divisors
i
, starting from 2 up to the square root ofx
. We use the square root as an optimization because ifx
is divisible by a number greater than its square root, the corresponding divisor (x // i
) will already have been counted. -
For each
i
within the loop:- We check if
i
dividesx
entirely (x % i == 0
). If it does, it meansi
is a divisor. - The count of divisors
cnt
is incremented, andi
is added to the sums
. - If
i
is not a perfect square ofx
(to avoid counting the same divisor twice), we incrementcnt
again and add the corresponding divisor (x // i
) to the sums
.
- We check if
-
After the loop, we check if the count of divisors
cnt
is exactly 4. If this condition holds true, the function returns the sums
, otherwise, it returns0
. -
In the main function
sumFourDivisors
, we aggregate the results by using a generator expressionf(x) for x in nums
inside thesum()
function. This expression calls functionf(x)
for every elementx
of the arraynums
. -
The
sum()
function calculates the cumulative sum of returned values byf(x)
(sum of divisors for qualified integers) and returns it.
To reiterate, data structures and patterns used in this approach include:
- A helper function to encapsulate the logic for evaluating individual numbers.
- Standard mathematical operations (modulo
%
, integer division//
, and square root) for divisor evaluation. - A generator expression to handle the accumulation of sums in a memory-efficient manner.
- Optimization by checking divisibility only up to the square root of the number to reduce redundant calculations.
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 consider an example array nums = [8, 10, 20]
to illustrate the solution approach:
-
We start by applying the function
f(x)
to each element innums
. -
For
x = 8
, the functionf(8)
tries to find divisors. We know that8
is a cube of the prime number2
, so its divisors are1
,2
,4
, and8
. Here the count of divisors is indeed 4. The sum of the divisors is1 + 2 + 4 + 8 = 15
. Since it has exactly four divisors, the functionf(8)
will return15
. -
For
x = 10
, the divisors are1
,2
,5
, and10
. Again, we have exactly four divisors. The sum is1 + 2 + 5 + 10 = 18
, and the functionf(10)
returns18
. -
For
x = 20
, the divisors are1
,2
,4
,5
,10
, and20
. There are more than four divisors, so the functionf(20)
does not meet the criteria and returns0
. -
Finally, the sum of all sums returned by
f(x)
for each element in the array is calculated. This is15 + 18 + 0 = 33
. -
Therefore, the
sumFourDivisors
function will return33
, as it is the sum of all the divisors of integers within the arraynums
that have exactly four divisors.
By using this step-by-step approach for each number in any given array nums
, we can efficiently find the sum of the divisors for numbers with exactly four divisors.
Solution Implementation
1class Solution:
2 def sumFourDivisors(self, nums: List[int]) -> int:
3 # Define a helper function to find if a number has exactly four divisors
4 def sum_if_four_divisors(num: int) -> int:
5 divisor = 2
6 count, sum_of_divisors = 2, num + 1 # start with 1 and 'num' as divisors
7 # Iterate through potential divisors starting from 2 up to the square root of 'num'
8 while divisor <= num // divisor:
9 if num % divisor == 0:
10 count += 1
11 sum_of_divisors += divisor
12 # Check if the divisor and its counterpart are different
13 if divisor * divisor != num:
14 count += 1
15 sum_of_divisors += num // divisor
16 divisor += 1
17 # If exactly 4 divisors have been found, return their sum, otherwise return 0
18 return sum_of_divisors if count == 4 else 0
19
20 # Sum the results of the helper function for each number in the input list 'nums'
21 return sum(sum_if_four_divisors(num) for num in nums)
22
1class Solution {
2
3 // Method to calculate the sum of all four divisors of the elements in the array.
4 public int sumFourDivisors(int[] nums) {
5 int sumTotal = 0; // Initialize the sum of the four divisors
6 for (int number : nums) {
7 sumTotal += sumOfFourDivisors(number); // Add the sum of the four divisors of the current number
8 }
9 return sumTotal; // Return the total sum
10 }
11
12 // Helper method to calculate the sum of four divisors of a single number.
13 private int sumOfFourDivisors(int number) {
14 int divisorCount = 2; // Start with 2 divisors: 1 and the number itself
15 int divisorSum = 1 + number; // Sum of divisors starts with 1 and the number
16
17 // Iterate to find other divisors
18 for (int i = 2; i <= number / i; ++i) {
19 // Check if 'i' is a divisor of 'number'
20 if (number % i == 0) {
21 divisorCount++; // Increase count of divisors
22 divisorSum += i; // Add 'i' to the sum of divisors
23 // Check if 'i' and 'number/i' are not the same divisor
24 if (i * i != number) {
25 divisorCount++; // If not, we have another divisor
26 divisorSum += number / i; // Add 'number/i' to the sum of divisors
27 }
28 }
29 }
30
31 // Return the sum of divisors only if exactly four divisors are found
32 return divisorCount == 4 ? divisorSum : 0;
33 }
34}
35
1class Solution {
2public:
3 // Function to sum the divisors of each number in the given vector
4 // that have exactly four distinct divisors.
5 int sumFourDivisors(vector<int>& nums) {
6 int totalSum = 0; // This will hold the sum of the divisors
7 // Iterate through all numbers in the given vector
8 for (int number : nums) {
9 totalSum += sumDivisorsIfFour(number);
10 }
11 return totalSum;
12 }
13
14 // Helper function to calculate the sum of divisors of a number
15 // if and only if it has exactly four distinct divisors.
16 int sumDivisorsIfFour(int number) {
17 int divisorCount = 2; // Start with 2 (1 and the number itself)
18 int sumOfDivisors = number + 1; // Include 1 and the number in the sum
19
20 // Iterate over possible divisors starting from 2 up to the square root of number
21 for (int i = 2; i <= number / i; ++i) {
22 if (number % i == 0) { // Check if i is a divisor
23 // Increment the divisor count and add it to the sum
24 ++divisorCount;
25 sumOfDivisors += i;
26 // Check if the divisor is not the square root of the number
27 if (i * i != number) {
28 // This means the quotient is also a divisor
29 ++divisorCount;
30 sumOfDivisors += number / i;
31 }
32 }
33 }
34
35 // If the number has exactly four divisors, return the sum
36 // Otherwise, return 0
37 return divisorCount == 4 ? sumOfDivisors : 0;
38 }
39};
40
1/**
2 * Function that returns the sum of four divisors for a single number
3 * @param x The number to find the sum of its four divisors
4 * @return The sum of the four divisors if there are exactly four, or 0 otherwise
5 */
6function sumOfDivisors(x: number): number {
7 // Start with 2 divisors (1 and the number itself) and their sum
8 let divisorCount = 2;
9 let sumOfDivisors = x + 1;
10
11 // Start from 2 to check for factors other than 1 and the number itself
12 for (let i = 2; i * i <= x; ++i) {
13 if (x % i === 0) {
14 // If i is a divisor, increment count and add it to the sum
15 ++divisorCount;
16 sumOfDivisors += i;
17
18 // If i is not a square root of x, account for the quotient as well
19 if (i * i !== x) {
20 ++divisorCount;
21 sumOfDivisors += Math.floor(x / i);
22 }
23 }
24 }
25
26 // If there are exactly 4 divisors, return the sum, otherwise, return 0
27 return divisorCount === 4 ? sumOfDivisors : 0;
28}
29
30/**
31 * Function that finds the sum of all numbers in the input array that have exactly four divisors
32 * @param nums Array of numbers
33 * @return The sum of numbers with only four divisors from the input array
34 */
35function sumFourDivisors(nums: number[]): number {
36 let totalSum = 0;
37
38 for (const num of nums) {
39 // For each number, calculate the sum of its four divisors if any
40 totalSum += sumOfDivisors(num);
41 }
42
43 // Return the total sum for the array
44 return totalSum;
45}
46
Time and Space Complexity
The time complexity of the solution is determined by two parts: the iteration through the list of numbers nums
, and the computation of the sum of four divisors for each number within the list.
The outer part of the code is a simple iteration through each number x
in nums, which has a complexity of O(n)
, where n
is the size of nums
.
The more complex part is the function f(x)
, which calculates the sum of the divisors for each number. The while loop within this function iterates over potential divisors from 2
to sqrt(x)
. In the worst-case scenario, this runs in O(sqrt(x))
time, because the number of divisors up to the square root of x
determines how many times the loop executes.
The total time complexity of this algorithm is a combination of the iteration through nums
and the divisor function applied to each element. Therefore, the time complexity is O(n * sqrt(x))
, where x
is the value of the largest number in nums
.
The space complexity of the provided code is O(1)
. Other than a few variables for intermediate calculations, the space used does not depend on the input size. The cnt
, s
, i
, and x
variables are reused for each function call, and no extra space that scales with the input size is allocated.
Learn more about how to find time and space complexity quickly using problem constraints.
Is the following code DFS or BFS?
1void search(Node root) { 2 if (!root) return; 3 visit(root); 4 root.visited = true; 5 for (Node node in root.adjacent) { 6 if (!node.visited) { 7 search(node); 8 } 9 } 10}
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
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.