Domain 2MediumMEDIUM

Four Divisors

LeetCode problem 1390: Four Divisors (medium).

Domain: medium•Updated: 2026-09-15
#Math

Problem Breakdown

We are given an array of integers nums. Our goal is to iterate through each number, determine if it possesses exactly four divisors, and if so, add up all its divisors (including 1 and itself) into a running total. If no numbers in the array meet this criteria, we return 0.

Key Constraints & Edge Cases:

  • Input Range: Numbers are between 11 and 10510^5. This is small enough that N\sqrt{N} iteration per number is efficient (≈320\approx 320 iterations max).
  • Array Size: Up to 10410^4 elements. Total operations roughly 3×1063 \times 10^6, which fits comfortably within standard time limits (typically ~1 second for Python on LeetCode).
  • Divisor Logic: We must distinguish between perfect squares and non-squares during iteration to avoid double-counting divisors when calculating the count or sum. For example, if n=4n=4 (222^2), 4=2\sqrt{4}=2. When we hit 2, it is its own pair; we shouldn’t add i twice for the divisor list but must ensure our logic correctly identifies that there are only 3 divisors total (1, 2, 4).
  • Overflow: While Python handles large integers automatically, in languages like C++ or Java, summing many divisors could exceed a standard 32-bit integer. We assume the return value fits within a 64-bit integer context implicitly handled by Python’s arbitrary precision ints.

Intuition

A naive approach would be to iterate from 11 up to num for every element in nums. This counts divisors and sums them, but it results in an Time Complexity of O(N⋅M)O(N \cdot M), where NN is the array length and MM is the maximum value (10510^5). With N=104N=10^4, this would be roughly 10910^9 operations—too slow.

Optimization: We know that divisors come in pairs (i,n/i)(i, n/i). If we find a divisor i, then n // i is also a divisor (unless they are the same). This allows us to iterate only up to n\sqrt{n}. This reduces complexity per number to O(M)O(\sqrt{M}), bringing total time complexity down to O(N⋅M)O(N \cdot \sqrt{M}).

Mathematical Insight: A number has exactly four divisors if and only if it is either:

  1. The product of two distinct primes (p1×p2p_1 \times p_2). Divisors are {1,p1,p2,n}\{1, p_1, p_2, n\}.
  2. The cube of a prime (p3p^3). Divisors are {1,p,p2,p3}\{1, p, p^2, p^3\}.

While we could check these properties via factorization or precomputed primes (Sieve), the square-root iteration is sufficient for this constraint set and demonstrates fundamental algorithmic thinking without unnecessary overhead. I will implement the optimized brute force approach as it’s cleaner to explain on a whiteboard.

Approach

  1. Initialize total_sum = 0.
  2. Iterate through each integer num in nums:
    • Initialize div_count = 0 and current_divisor_sum = 0.
    • Loop variable i from 11 to int(num)+1\text{int}(\sqrt{\text{num}}) + 1.
    • If num % i == 0:
      • Identify the pair: d1 = i, d2 = num // i.
      • Check if it’s a perfect square case (i == d2).
        • If distinct: Increment div_count by 2. Add both d1 + d2 to current_divisor_sum.
        • If same (perfect square): Increment div_count by 1. Add d1 to current_divisor_sum.
    • After the loop, check if div_count == 4.
      • If true: add current_divisor_sum to total_sum.
  3. Return total_sum.

Complexity Analysis

  • Time Complexity: O(N⋅M)O(N \cdot \sqrt{M}), where NN is the number of elements in nums and MM is the maximum value (10510^5). With given constraints, this results in approximately 3.2×1063.2 \times 10^6 operations, which is well within acceptable limits for Python (typically allowing ∼107−108\sim 10^7-10^8 ops/sec).
  • Space Complexity: O(1)O(1) auxiliary space. We only use a few variables to track counts and sums regardless of input size.

Solution

import math

class Solution:
    def sumFourDivisors(self, nums):
        total_sum = 0
        
        for num in nums:
            div_count = 0
            current_divisor_sum = 0
            
            # Iterate from 1 to sqrt(num)
            limit = int(math.isqrt(num)) + 1
            
            for i in range(1, limit):
                if num % i == 0:
                    d2 = num // i
                    
                    if i != d2:
                        div_count += 2
                        current_divisor_sum += (i + d2)
                    else:
                        # Perfect square case handled here implicitly by loop range logic, 
                        # but we must ensure count is correct. 
                        # Since limit = sqrt(num), the last iteration i == sqrt(num).
                        div_count += 1
                        current_divisor_sum += i
            
            if div_count == 4:
                total_sum += current_divisor_sum
                
        return total_sum

Edge Cases Handled

  • Perfect Squares: The logic if i != d2 correctly handles perfect squares (e.g., n=9n=9). When i=3i=3, d1=d2d_1=d_2. We increment count by 1 instead of 2, ensuring the divisor list isn’t double-counted.
  • Primes: A prime number has divisors {1,n}\{1, n\}. The loop finds only i=1 (where d2=nd_2=n). Count becomes 2. Condition div_count == 4 fails correctly.
  • Small Numbers (<5<5): Numbers like 1, 2, 3 cannot have four divisors naturally. The logic holds as count will be ≤2\le 2. Number 4 has 3 divisors (count=3). Smallest number with 4 divisors is 6 or 8; the loop correctly identifies these.
  • Empty Array: Loop over nums simply doesn’t execute, returns initialized total_sum = 0.