Code Implementation

class Solution:
    def sumFourDivisors(self, nums):
        def four_divisor_sum(n):
            divisors = set()
            for i in range(1, int(n ** 0.5) + 1):
                if n % i == 0:
                    divisors.add(i)
                    divisors.add(n // i)
                    if len(divisors) > 4:
                        return 0
            return sum(divisors) if len(divisors) == 4 else 0

        total = 0
        for num in nums:
            total += four_divisor_sum(num)
        return total
      

class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int total = 0;
        for (int num : nums) {
            unordered_set<int> divisors;
            for (int i = 1; i * i <= num; ++i) {
                if (num % i == 0) {
                    divisors.insert(i);
                    divisors.insert(num / i);
                    if (divisors.size() > 4) break;
                }
            }
            if (divisors.size() == 4) {
                int sum = 0;
                for (int d : divisors) sum += d;
                total += sum;
            }
        }
        return total;
    }
};
      

class Solution {
    public int sumFourDivisors(int[] nums) {
        int total = 0;
        for (int num : nums) {
            HashSet<Integer> divisors = new HashSet<>();
            for (int i = 1; i * i <= num; i++) {
                if (num % i == 0) {
                    divisors.add(i);
                    divisors.add(num / i);
                    if (divisors.size() > 4) break;
                }
            }
            if (divisors.size() == 4) {
                int sum = 0;
                for (int d : divisors) sum += d;
                total += sum;
            }
        }
        return total;
    }
}
      

var sumFourDivisors = function(nums) {
    let total = 0;
    for (let num of nums) {
        let divisors = new Set();
        for (let i = 1; i * i <= num; i++) {
            if (num % i === 0) {
                divisors.add(i);
                divisors.add(num / i);
                if (divisors.size > 4) break;
            }
        }
        if (divisors.size === 4) {
            let sum = 0;
            for (let d of divisors) sum += d;
            total += sum;
        }
    }
    return total;
};
      

Problem Description

Given an array of positive integers nums, your task is to find the sum of all divisors of every integer in the array that has exactly four divisors. If a number in nums has exactly four divisors, add the sum of those divisors to your total; otherwise, ignore it. Return the final total sum.

• Each number in nums is a positive integer.
• Only numbers with exactly four divisors contribute to the sum.
• If a number has any number of divisors other than four, it does not contribute.
• You may not reuse elements; each number is considered independently.

Thought Process

The main challenge is to efficiently identify numbers with exactly four divisors and calculate their sum. A brute-force approach would be to count all the divisors for each number in nums, but that can be slow for large numbers. Instead, we look for a pattern or shortcut.

Notice that a number with exactly four divisors must have a specific structure. For example, if n is a product of two distinct primes (p * q), its divisors are 1, p, q, n. Similarly, if n = p^3 for some prime p, its divisors are 1, p, p^2, p^3. Recognizing these patterns helps us optimize our solution.

Our goal is to avoid unnecessary computation by stopping early if a number has more than four divisors, and only summing divisors when exactly four are found.

Solution Approach

• Iterate through each number in nums:
  • For each number, initialize a set to store its divisors.
• Find divisors efficiently:
  • Loop from 1 to the square root of the number.
  • If i divides the number, add both i and num / i to the set of divisors.
  • If the set size exceeds 4, break early (since we only care about numbers with exactly four divisors).
• Sum divisors if count is exactly four:
  • If the set has exactly four elements, sum them and add to the running total.
• Return the total sum:
  • After processing all numbers, return the final total.

This approach is efficient because it avoids unnecessary work by breaking early and leverages the mathematical structure of numbers with exactly four divisors.

Example Walkthrough

Suppose nums = [21, 4, 7].

• 21:
  • Divisors: 1, 3, 7, 21 (exactly four)
  • Sum: 1 + 3 + 7 + 21 = 32
  • Add 32 to total.
• 4:
  • Divisors: 1, 2, 4 (only three)
  • Not counted.
• 7:
  • Divisors: 1, 7 (only two)
  • Not counted.

The final answer is 32.

Time and Space Complexity

• Brute-force approach:
  • For each number, check all numbers from 1 to n to find divisors. This is O(n) per number, leading to O(N * M) where N is the length of nums and M is the largest number in nums.
• Optimized approach:
  • For each number, only check up to sqrt(n). So, per number, work is O(sqrt(M)), leading to O(N * sqrt(M)) for the whole array.
  • Space: We use a set of at most 4 elements per number, so space is O(1) per number, and O(1) overall (ignoring input and output).

Summary

To solve the Four Divisors problem, we combine mathematical insight with efficient programming. By recognizing that only numbers with exactly four divisors matter, and that these numbers have a specific structure, we can avoid brute-force enumeration. Using a set to track divisors and breaking early when unnecessary, we efficiently sum the divisors for qualifying numbers. This approach is both simple and elegant, leveraging properties of divisors and early exits for optimal performance.