LeetCode 1390 - Four Divisors

Difficulty: 🟡 Medium
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to calculate the sum of divisors for numbers in a given integer array nums, but only for those numbers that have exactly four divisors. For each number n in nums, we need to determine all its divisors, check if there are exactly four, and if so, sum them up. The output is the total sum across all qualifying numbers. If no number has exactly four divisors, the result should be 0.

The input array nums has length up to 10^4, and each element is up to 10^5. This scale suggests that a naive approach that checks all numbers up to n for divisors could be too slow because it would be O(n * sqrt(max(nums))) in the worst case. Efficient checking of divisors is critical.

Important edge cases include numbers with fewer than four divisors (like primes or 1), numbers with exactly four divisors (like 6, 10, 14, 21), duplicates in the array, and the smallest or largest allowed numbers.

Approaches

Brute Force

A brute-force solution iterates through each number in nums and finds all divisors by checking every integer from 1 to n. We collect divisors, count them, and if there are exactly four, sum them and add to the total. While correct, this method is inefficient because for large numbers up to 10^5, iterating up to n or even sqrt(n) for every number can lead to up to 10^4 * 316 operations, which is borderline acceptable but not ideal for time-sensitive scenarios.

Optimal Approach

The key observation is that a number with exactly four divisors has a specific form:

It is a product of two distinct primes: p * q where p != q. Its divisors are {1, p, q, p*q}.
It is a cube of a prime: p^3. Its divisors are {1, p, p^2, p^3}.

Instead of checking all divisors for every number, we can efficiently check if a number is of one of these two forms using a prime list generated up to sqrt(max(nums)). Once we detect the form, computing the sum of the four divisors is straightforward.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * sqrt(max(nums)))	O(1)	Checks each number for divisors up to sqrt(n)
Optimal	O(n * sqrt(n))	O(sqrt(max(nums)))	Uses prime checking and properties of numbers with exactly four divisors

Algorithm Walkthrough

Generate all prime numbers up to sqrt(max(nums)) using the Sieve of Eratosthenes. This allows efficient prime checking and factorization.
Initialize a variable total_sum to store the cumulative sum of divisors.
Iterate through each number num in nums.
For each num, attempt to determine its prime factorization up to sqrt(num).
Check if num is of the form p^3 (cube of a prime) or p * q (product of two distinct primes).
If it is, calculate the sum of its four divisors using the formulas above and add it to total_sum.
Return total_sum after processing all numbers.

Why it works: Numbers with exactly four divisors fall into these two categories. By directly identifying numbers of these forms, we avoid unnecessary divisor counting and guarantee correctness.

Python Solution

from typing import List
import math

class Solution:
    def sumFourDivisors(self, nums: List[int]) -> int:
        def sieve(limit: int) -> List[int]:
            is_prime = [True] * (limit + 1)
            is_prime[0] = is_prime[1] = False
            for i in range(2, int(limit**0.5) + 1):
                if is_prime[i]:
                    for j in range(i*i, limit+1, i):
                        is_prime[j] = False
            return [i for i, val in enumerate(is_prime) if val]
        
        primes = sieve(int(max(nums)**0.5) + 1)
        prime_set = set(primes)
        total_sum = 0
        
        for num in nums:
            found = False
            for p in primes:
                if p * p * p > num:
                    break
                if num % p == 0:
                    q = num // p
                    if q == p * p:  # case p^3
                        total_sum += 1 + p + p*p + p*p*p
                        found = True
                        break
                    elif q in prime_set and q != p:  # case p*q
                        total_sum += 1 + p + q + num
                        found = True
                        break
            # special case when num is a perfect cube of a prime larger than sqrt(num)
            if not found:
                cube_root = round(num ** (1/3))
                if cube_root ** 3 == num:
                    # check if cube_root is prime
                    if all(cube_root % d != 0 for d in range(2, int(cube_root**0.5)+1)):
                        total_sum += 1 + cube_root + cube_root**2 + cube_root**3
        
        return total_sum

Explanation: The sieve function generates all primes up to the square root of the maximum number. For each number, we check if it is either p^3 or p*q using the primes list. If so, we compute the sum of its four divisors and add it to the total.

Go Solution

package main

import (
    "math"
)

func sumFourDivisors(nums []int) int {
    maxNum := 0
    for _, n := range nums {
        if n > maxNum {
            maxNum = n
        }
    }

    // Sieve of Eratosthenes
    limit := int(math.Sqrt(float64(maxNum))) + 1
    isPrime := make([]bool, limit+1)
    for i := 2; i <= limit; i++ {
        isPrime[i] = true
    }
    for i := 2; i*i <= limit; i++ {
        if isPrime[i] {
            for j := i * i; j <= limit; j += i {
                isPrime[j] = false
            }
        }
    }
    primes := []int{}
    primeSet := make(map[int]bool)
    for i := 2; i <= limit; i++ {
        if isPrime[i] {
            primes = append(primes, i)
            primeSet[i] = true
        }
    }

    totalSum := 0
    for _, num := range nums {
        found := false
        for _, p := range primes {
            if p*p*p > num {
                break
            }
            if num%p == 0 {
                q := num / p
                if q == p*p {
                    totalSum += 1 + p + p*p + p*p*p
                    found = true
                    break
                } else if primeSet[q] && q != p {
                    totalSum += 1 + p + q + num
                    found = true
                    break
                }
            }
        }
        if !found {
            cubeRoot := int(math.Round(math.Pow(float64(num), 1.0/3.0)))
            if cubeRoot*cubeRoot*cubeRoot == num {
                isCubePrime := true
                for d := 2; d*d <= cubeRoot; d++ {
                    if cubeRoot%d == 0 {
                        isCubePrime = false
                        break
                    }
                }
                if isCubePrime {
                    totalSum += 1 + cubeRoot + cubeRoot*cubeRoot + num
                }
            }
        }
    }
    return totalSum
}

Explanation: The Go implementation mirrors the Python logic with careful type handling and explicit integer rounding. It uses slices for primes and maps for quick prime lookup. Edge cases with perfect cubes beyond the sieve limit are handled with direct prime checking.

Worked Examples

Example 1: nums = [21,4,7]

21: factors are 1, 3, 7, 21 → exactly four divisors → sum = 32
4: factors are 1, 2, 4 → three divisors → ignored
7: prime → two divisors → ignored

total_sum = 32

Example 2: nums = [21,21]

Both 21: sum of divisors = 32 each → total = 64

Example 3: nums = [1,2,3,4,5]

No number has exactly four divisors → total = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * sqrt(max(nums)))	For each number, we factorize up to sqrt(num) and check prime combinations.
Space	O(sqrt(max(nums)))	We store primes up to sqrt(max(nums)) for factorization.

This complexity is feasible given the constraints, with n <= 10^4 and nums[i] <= 10^5.