Problem statement

Given an integer array nums, look at the integers in it that have exactly four positive divisors. Return the sum of all the divisors of those integers.

If no integer in nums has exactly four divisors, return 0. Repeated values are counted each time they appear.

Example 1

Input: nums = [21,4,7]
Output: 32
Explanation: 21 has divisors 1, 3, 7, 21 (sum 32). 4 has three divisors and 7 has two.

Example 2

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

Example 3

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

Constraints

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

Hints for Four Divisors

1. Hint 1

   Divisors come in pairs d and x / d, with one of the pair at most sqrt(x).

2. Hint 2

   Enumerate d up to sqrt(x), counting and summing both members of each pair (once if d * d == x).

3. Hint 3

   Stop as soon as the count passes 4 — most numbers are discarded quickly.

How to solve Four Divisors

Enumerate divisors in pairs up to the square root, keep a count and a running sum, and give up on a number as soon as it has more than four.

Approach

1. For each x in nums, set count = 0 and s = 0.
2. For d = 1, 2, … while d * d <= x: if d divides x, add d and x / d to s and 2 to count (only d and 1 if d * d == x). Break if count > 4.
3. If count == 4, add s to the answer.
4. Return the answer.

Why it works

Every divisor e of x pairs with x / e, and exactly one member of each pair is at most √x (both are, when e = √x). So scanning d ≤ √x meets every divisor once through its pair, giving the exact count and sum. Numbers with exactly four divisors are p·q for distinct primes or p³, but the scan does not need that characterisation.

Complexity

• Time — O(n · √M) where M is the largest value
• Space — O(1)

Pitfalls

• Perfect squares: d = √x must be counted once, not twice (4 has divisors 1, 2, 4).
• Summing divisors of numbers that turn out not to have four — keep the sum local to each number.
• Repeated values each contribute.

Reference solution

Python

from typing import List

def sumFourDivisors(nums: List[int]) -> int:
    total = 0
    for x in nums:
        count = 0
        s = 0
        d = 1
        while d * d <= x:
            if x % d == 0:
                other = x // d
                if other == d:
                    count += 1
                    s += d
                else:
                    count += 2
                    s += d + other
                if count > 4:
                    break
            d += 1
        if count == 4:
            total += s
    return total

Java

public static int sumFourDivisors(int[] nums) {
    int total = 0;
    for (int x : nums) {
        int count = 0, s = 0;
        for (int d = 1; d * d <= x; d++) {
            if (x % d != 0) continue;
            int other = x / d;
            if (other == d) {
                count += 1;
                s += d;
            } else {
                count += 2;
                s += d + other;
            }
            if (count > 4) break;
        }
        if (count == 4) total += s;
    }
    return total;
}

C++

int sumFourDivisors(vector<int>& nums) {
    int total = 0;
    for (int x : nums) {
        int count = 0, s = 0;
        for (int d = 1; d * d <= x; d++) {
            if (x % d != 0) continue;
            int other = x / d;
            if (other == d) {
                count += 1;
                s += d;
            } else {
                count += 2;
                s += d + other;
            }
            if (count > 4) break;
        }
        if (count == 4) total += s;
    }
    return total;
}

JavaScript

var sumFourDivisors = function(nums) {
    var total = 0;
    for (var i = 0; i < nums.length; i++) {
        var x = nums[i], count = 0, s = 0;
        for (var d = 1; d * d <= x; d++) {
            if (x % d !== 0) continue;
            var other = x / d;
            if (other === d) {
                count += 1;
                s += d;
            } else {
                count += 2;
                s += d + other;
            }
            if (count > 4) break;
        }
        if (count === 4) total += s;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium