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 the Solution class, which takes an integer x as input and returns the sum of its divisors if it has exactly four divisors, otherwise returns 0.
Inside the function f(x), we initialize two variables: cnt to count the number of divisors (starting with 2, to account for '1' and x itself), and s to keep the sum of divisors (initialized to x + 1 for the same reason).
A while loop is used to iterate over possible divisors i, starting from 2 up to the square root of x. We use the square root as an optimization because if x 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 divides x entirely (x % i == 0). If it does, it means i is a divisor.
- The count of divisors cnt is incremented, and i is added to the sum s.
- If i is not a perfect square of x (to avoid counting the same divisor twice), we increment cnt again and add the corresponding divisor (x // i) to the sum s.
After the loop, we check if the count of divisors cnt is exactly 4. If this condition holds true, the function returns the sum s, otherwise, it returns 0.
In the main function sumFourDivisors, we aggregate the results by using a generator expression f(x) for x in nums inside the sum() function. This expression calls function f(x) for every element x of the array nums.
The sum() function calculates the cumulative sum of returned values by f(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 Evaluator

Example 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 in nums.
For x = 8, the function f(8) tries to find divisors. We know that 8 is a cube of the prime number 2, so its divisors are 1, 2, 4, and 8. Here the count of divisors is indeed 4. The sum of the divisors is 1 + 2 + 4 + 8 = 15. Since it has exactly four divisors, the function f(8) will return 15.
For x = 10, the divisors are 1, 2, 5, and 10. Again, we have exactly four divisors. The sum is 1 + 2 + 5 + 10 = 18, and the function f(10) returns 18.
For x = 20, the divisors are 1, 2, 4, 5, 10, and 20. There are more than four divisors, so the function f(20) does not meet the criteria and returns 0.
Finally, the sum of all sums returned by f(x) for each element in the array is calculated. This is 15 + 18 + 0 = 33.
Therefore, the sumFourDivisors function will return 33, as it is the sum of all the divisors of integers within the array nums 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know