Solution Explanation for LeetCode 1390: Four Divisors

This problem asks us to find the sum of divisors for all numbers in an array that have exactly four divisors. A number with exactly four divisors must be of the form p³ (where p is a prime number) or pq (where p and q are distinct prime numbers).

Approach: Efficient Factorization

The most efficient approach involves a slightly optimized factorization method. We don't need to find all divisors; we only care if there are exactly four.

1. Prime Factorization (Optimized): We iterate up to the square root of the number (x). If i divides x, it's a factor. We add i and x/i to the sum of divisors (s). The condition i * i != x prevents double-counting when i is the square root of a perfect square.

2. Divisor Count: We keep track of the number of divisors (cnt). We start at 2 (1 and the number itself are always divisors). Each time we find a factor i, we increment cnt by 1 or 2 (depending on whether i*i == x).

3. Four Divisors Check: After iterating through potential factors, if cnt == 4, we have found a number with exactly four divisors, and we return its sum of divisors (s). Otherwise, we return 0.

4. Summing Results: The main function iterates through the input array, applying the f(x) function (the factorization step) to each number and summing the results.

Time and Space Complexity

• Time Complexity: O(n√m), where n is the length of the input array nums, and m is the maximum value in nums. The dominant factor is the factorization process, which takes up to O(√m) time for each number.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.

Code Implementation (Python)

class Solution:
    def sumFourDivisors(self, nums: List[int]) -> int:
        def f(x: int) -> int:
            i = 2
            cnt, s = 2, x + 1  # Initialize cnt to 2 (1 and x are always divisors)
            while i * i <= x: # Optimization: Iterate up to sqrt(x)
                if x % i == 0:
                    cnt += 1
                    s += i
                    if i * i != x:
                        cnt += 1
                        s += x // i
                i += 1
            return s if cnt == 4 else 0
 
        return sum(f(x) for x in nums)

The other language implementations (Java, C++, Go, TypeScript) follow the same logic with minor syntax variations. The core factorization and divisor counting remain consistent across all implementations.