Four Divisors

Problem

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors. If there is no such integer in the array, return 0.

Examples

Example 1

1
2
3
4
5
6
7


Input: nums = [21,4,7]
Output: 32
Explanation: 
21 has 4 divisors: 1, 3, 7, 21
4 has 3 divisors: 1, 2, 4
7 has 2 divisors: 1, 7
The answer is the sum of divisors of 21 only.

Example 2

1
2


Input: nums = [21,21]
Output: 64

Example 3

1
2


Input: nums = [1,2,3,4,5]
Output: 0

Constraints

1 <= nums.length <= 10^4
1 <= nums[i] <= 10^5

Solution

Method 1 – Brute Force Divisor Counting

Intuition

A number has exactly four divisors if and only if it is the product of two distinct primes (p * q), or a cube of a prime (p^3). We can check all divisors for each number and sum them if there are exactly four.

Approach

For each number in nums, count its divisors and sum them if it has exactly four divisors.
For each number, iterate from 1 to sqrt(num) to find divisors efficiently.
If the number of divisors is exactly four, add their sum to the answer.
Return the total sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int ans = 0;
        for (int x : nums) {
            int cnt = 0, sum = 0;
            for (int d = 1; d * d <= x; ++d) {
                if (x % d == 0) {
                    int d2 = x / d;
                    if (d == d2) {
                        cnt++;
                        sum += d;
                    } else {
                        cnt += 2;
                        sum += d + d2;
                    }
                }
            }
            if (cnt == 4) ans += sum;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


type Solution struct{}
func (Solution) sumFourDivisors(nums []int) int {
    ans := 0
    for _, x := range nums {
        cnt, sum := 0, 0
        for d := 1; d*d <= x; d++ {
            if x%d == 0 {
                d2 := x / d
                if d == d2 {
                    cnt++
                    sum += d
                } else {
                    cnt += 2
                    sum += d + d2
                }
            }
        }
        if cnt == 4 {
            ans += sum
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
    public int sumFourDivisors(int[] nums) {
        int ans = 0;
        for (int x : nums) {
            int cnt = 0, sum = 0;
            for (int d = 1; d * d <= x; ++d) {
                if (x % d == 0) {
                    int d2 = x / d;
                    if (d == d2) {
                        cnt++;
                        sum += d;
                    } else {
                        cnt += 2;
                        sum += d + d2;
                    }
                }
            }
            if (cnt == 4) ans += sum;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    fun sumFourDivisors(nums: IntArray): Int {
        var ans = 0
        for (x in nums) {
            var cnt = 0
            var sum = 0
            var d = 1
            while (d * d <= x) {
                if (x % d == 0) {
                    val d2 = x / d
                    if (d == d2) {
                        cnt++
                        sum += d
                    } else {
                        cnt += 2
                        sum += d + d2
                    }
                }
                d++
            }
            if (cnt == 4) ans += sum
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def sumFourDivisors(self, nums: list[int]) -> int:
        ans = 0
        for x in nums:
            cnt, s = 0, 0
            for d in range(1, int(x ** 0.5) + 1):
                if x % d == 0:
                    d2 = x // d
                    if d == d2:
                        cnt += 1
                        s += d
                    else:
                        cnt += 2
                        s += d + d2
            if cnt == 4:
                ans += s
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


impl Solution {
    pub fn sum_four_divisors(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        for &x in &nums {
            let (mut cnt, mut sum) = (0, 0);
            let mut d = 1;
            while d * d <= x {
                if x % d == 0 {
                    let d2 = x / d;
                    if d == d2 {
                        cnt += 1;
                        sum += d;
                    } else {
                        cnt += 2;
                        sum += d + d2;
                    }
                }
                d += 1;
            }
            if cnt == 4 {
                ans += sum;
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
  sumFourDivisors(nums: number[]): number {
    let ans = 0;
    for (const x of nums) {
      let cnt = 0, sum = 0;
      for (let d = 1; d * d <= x; d++) {
        if (x % d === 0) {
          const d2 = Math.floor(x / d);
          if (d === d2) {
            cnt++;
            sum += d;
          } else {
            cnt += 2;
            sum += d + d2;
          }
        }
      }
      if (cnt === 4) ans += sum;
    }
    return ans;
  }
}

Complexity

⏰ Time complexity: O(n * sqrt(m)), where n is the length of nums and m is the maximum value in nums, since we check up to sqrt(x) for each x.
🧺 Space complexity: O(1), as only a few variables are used.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Brute Force Divisor Counting#

Intuition#

Approach#

Code#

Complexity#