Leetcode 1390. Four Divisors

Problem Explanation:

The problem requires us to find the sum of divisors of the integers in an array that have exactly four divisors. If we don't find any such integer, we should return 0.

Let's take an example for better understanding. Consider an array nums = [21,4,7]. The integer 21 has four divisors [1, 3, 7, 21], number 4 has three divisors [1,2,4], and number 7 has two divisors [1,7]. As we can see only number 21 has exactly four divisors, so our answer will be the sum of divisors of 21 which is 32 hence the output is 32.

Approach Explanation:

We can solve this problem by using number theory and brute force. We iterate over the array of numbers. For each number, we use a brute force approach to find the divisors. If we find a number that has only one divisor apart from 1 and itself, this number has four divisors. This is because a number with more than one divisor other than 1 and itself will have more than four divisors in total. Whenever we find such a number, we add to the answer the sum of its four divisors: 1, the number, divisor, and number / divisor.

C++ Solution:

1
2cpp
3class Solution {
4 public:
5  int sumFourDivisors(vector<int>& nums) {
6    int ans = 0;
7
8    for (int num : nums) {
9      int divisor = 0;
10      // Checking for divisors
11      for (int i = 2; i * i <= num; ++i)
12        if (num % i == 0) {
13          if (divisor == 0)
14            divisor = i;
15          else {
16            divisor = 0;
17            break;
18          }
19        }
20      // A number has exactly four divisors only when the number has one divisor apart from 1 and num
21      if (divisor > 0 && divisor * divisor < num)
22        ans += 1 + num + divisor + num / divisor;
23    }
24
25    return ans;
26  }
27};

Python solution:

1
2python
3class Solution:
4    def sumFourDivisors(self, nums: List[int]) -> int:
5        ans = 0
6        for num in nums:
7            divisor = 0
8            # Checking for divisors
9            for i in range(2, int(num ** 0.5)+1):
10                if num % i == 0: 
11                    if divisor == 0: 
12                        divisor = i 
13                    else: 
14                        divisor = 0 
15                        break 
16            # A number has exactly four divisors only when the number has one divisor apart from 1 and num
17            if divisor > 0 and divisor * divisor < num:
18                ans += 1 + num + divisor + num // divisor 
19        return ans

Java Solution:

1
2java
3class Solution {
4    public int sumFourDivisors(int[] nums) {
5        int ans = 0;
6        for (int num : nums) {
7            int divisor = 0;
8            // Checking for divisors
9            for (int i = 2; i * i <= num; ++i) 
10                if (num % i == 0) {
11                    if (divisor != 0) {
12                        divisor = 0;
13                        break;
14                    }
15                    divisor = i;
16                }
17            // A number has exactly four divisors only when the number has one divisor apart from 1 and num
18            if (divisor > 0 && divisor * divisor < num)
19                ans += 1 + num + divisor + num / divisor;
20        }
21        return ans;
22    }
23}

JavaScript Solution:

1
2javascript
3class Solution {
4    sumFourDivisors(nums) {
5        let ans = 0;
6        for (let num of nums) {
7            let divisor = 0;
8            // Checking for divisors
9            for (let i = 2; i * i <= num; ++i)
10                if (num % i === 0) {
11                    if (divisor !== 0) {
12                        divisor = 0;
13                        break;
14                    }
15                    divisor = i;
16                }
17            // A number has exactly four divisors only when the number has one divisor apart from 1 and num
18            if (divisor > 0 && divisor * divisor < num)
19                ans += 1 + num + divisor + num / divisor;
20        }
21
22        return ans;
23    }
24}
25
26let sol = new Solution();
27console.log(sol.sumFourDivisors([21,19,2]));

In the JavaScript solution, we create a class Solution which has a method sumFourDivisors. This function iterates over each number in the given array. For each number, it finds the divisors. If a number has exactly four divisors, then that number is added to the ans variable along with the summation of its divisors.

At the end, the function sumFourDivisors returns the final sum ans which is the sum of divisors of the integers that have exactly four divisors.

We create an instance sol of the class Solution and call the method sumFourDivisors on the created instance by passing an array which we want to test against.

In conclusion, all of these solutions use a similar approach but in different programming languages. The algorithm of finding divisors in the given integers is the same, the only difference is the different ways it is implemented and expressed in various programming languages including JavaScript, Java, Python, and C++.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫