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 and . This is small enough that iteration per number is efficient ( iterations max).
- Array Size: Up to elements. Total operations roughly , 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 (), . When we hit 2, it is its own pair; we shouldn’t add
itwice 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 up to num for every element in nums. This counts divisors and sums them, but it results in an Time Complexity of , where is the array length and is the maximum value (). With , this would be roughly operations—too slow.
Optimization:
We know that divisors come in pairs . 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 . This reduces complexity per number to , bringing total time complexity down to .
Mathematical Insight: A number has exactly four divisors if and only if it is either:
- The product of two distinct primes (). Divisors are .
- The cube of a prime (). Divisors are .
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
- Initialize
total_sum = 0. - Iterate through each integer
numinnums:- Initialize
div_count = 0andcurrent_divisor_sum = 0. - Loop variable
ifrom to . - 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_countby 2. Add bothd1 + d2tocurrent_divisor_sum. - If same (perfect square): Increment
div_countby 1. Addd1tocurrent_divisor_sum.
- If distinct: Increment
- Identify the pair:
- After the loop, check if
div_count == 4.- If true: add
current_divisor_sumtototal_sum.
- If true: add
- Initialize
- Return
total_sum.
Complexity Analysis
- Time Complexity: , where is the number of elements in
numsand is the maximum value (). With given constraints, this results in approximately operations, which is well within acceptable limits for Python (typically allowing ops/sec). - Space Complexity: 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 != d2correctly handles perfect squares (e.g., ). When , . We increment count by 1 instead of 2, ensuring the divisor list isn’t double-counted. - Primes: A prime number has divisors . The loop finds only
i=1(where ). Count becomes 2. Conditiondiv_count == 4fails correctly. - Small Numbers (): Numbers like 1, 2, 3 cannot have four divisors naturally. The logic holds as count will be . 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
numssimply doesn’t execute, returns initializedtotal_sum = 0.