Problem Description

You are given an integer array nums. Your task is to find all integers in the array that have exactly four divisors, and return the sum of all divisors for those integers.

A divisor of a number is any integer that divides the number evenly (with no remainder). For example, the divisors of 12 are 1, 2, 3, 4, 6, 12 (which is 6 divisors total, so it wouldn't qualify).

The key requirements are:

• Check each integer in the array to see if it has exactly 4 divisors
• If an integer has exactly 4 divisors, add up all its divisors
• Return the total sum of all divisors from all qualifying integers
• If no integer in the array has exactly 4 divisors, return 0

For example:

• The number 21 has divisors 1, 3, 7, 21 (exactly 4 divisors), so we would add 1 + 3 + 7 + 21 = 32 to our answer
• The number 8 has divisors 1, 2, 4, 8 (exactly 4 divisors), so we would add 1 + 2 + 4 + 8 = 15 to our answer
• The number 6 has divisors 1, 2, 3, 6 (exactly 4 divisors), so we would add 1 + 2 + 3 + 6 = 12 to our answer

The solution works by iterating through each number in the array, finding all its divisors, and checking if the count equals 4. If it does, the sum of those divisors is added to the final result.

Intuition

The core insight is that we need to find all divisors of each number efficiently. When looking for divisors of a number x, we don't need to check every number from 1 to x. Instead, we can leverage a key mathematical property: divisors come in pairs.

For any divisor i of x, there's a corresponding divisor x/i. For example, if 12 is divisible by 3, then 12/3 = 4 is also a divisor. This means we only need to check numbers up to √x, because after that point, we'd be finding the same pairs in reverse order.

When we find a divisor i, we can immediately know that both i and x/i are divisors. This allows us to:

1. Count 2 divisors at once (in most cases)
2. Add both divisors to our sum simultaneously

There's one special case to handle: when i * i = x (perfect squares). In this case, i and x/i are the same number, so we should only count it once.

We start with a count of 2 and sum of x + 1 because every number has at least two divisors: 1 and itself. Then we iterate from 2 to √x to find any additional divisor pairs.

The efficiency comes from the fact that we're only iterating up to √x instead of x, which significantly reduces the number of operations for large numbers. Once we've found all divisors and counted them, we simply check if the count equals 4. If it does, we return the sum; otherwise, we return 0.

This approach is applied to each number in the array independently, and the final answer is the sum of all individual results.

Learn more about Math patterns.

Solution Approach

The solution implements a factor decomposition approach to find all divisors of each number in the array.

The main function iterates through each number in nums and applies a helper function f(x) that:

1. Initializes counters and sum:

   • cnt = 2 (starting with 2 because every number has at least two divisors: 1 and itself)
   • s = x + 1 (sum starts with 1 + x)
   • i = 2 (start checking from 2)

2. Iterates up to √x: The loop condition i <= x // i is equivalent to i <= √x, but avoids floating-point operations. This optimization reduces time complexity from O(n) to O(√n) for each number.

3. Checks for divisibility: For each i, if x % i == 0, then i is a divisor:

   • Increment the count by 1 and add i to the sum
   • Check if i * i != x (not a perfect square case):
     • If true, we've found a pair of divisors: i and x // i
     • Increment count by 1 more and add x // i to the sum
   • This handles both divisors in a pair simultaneously

4. Returns conditional result: After checking all potential divisors:

   • If cnt == 4, return the sum s (this number has exactly 4 divisors)
   • Otherwise, return 0 (doesn't meet the requirement)

5. Aggregates results: The main function uses sum(f(x) for x in nums) to apply the helper function to each number and sum all the results.

The algorithm efficiently handles edge cases:

• Perfect squares are correctly handled by the i * i != x check
• Numbers with fewer or more than 4 divisors return 0
• The integer division x // i ensures we work with integers throughout

Time complexity: O(n * √m) where n is the length of the array and m is the maximum value in the array. Space complexity: O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with nums = [21, 6, 8].

Processing first number: 21

1. Initialize: cnt = 2, s = 21 + 1 = 22 (accounting for divisors 1 and 21)
2. Check i = 2: 21 % 2 ≠ 0, not a divisor, continue
3. Check i = 3: 21 % 3 = 0, so 3 is a divisor
   • Increment cnt to 3, add 3 to sum: s = 22 + 3 = 25
   • Since 3 * 3 ≠ 21, we also have divisor 21 // 3 = 7
   • Increment cnt to 4, add 7 to sum: s = 25 + 7 = 32
4. Check i = 4: 4 * 4 = 16 < 21, so continue
   • 21 % 4 ≠ 0, not a divisor
5. Stop at i = 5 since 5 * 5 = 25 > 21
6. Final: cnt = 4, so return sum of 32

Processing second number: 6

1. Initialize: cnt = 2, s = 6 + 1 = 7 (divisors 1 and 6)
2. Check i = 2: 6 % 2 = 0, so 2 is a divisor
   • Increment cnt to 3, add 2 to sum: s = 7 + 2 = 9
   • Since 2 * 2 ≠ 6, we also have divisor 6 // 2 = 3
   • Increment cnt to 4, add 3 to sum: s = 9 + 3 = 12
3. Stop at i = 3 since 3 * 3 = 9 > 6
4. Final: cnt = 4, so return sum of 12

Processing third number: 8

1. Initialize: cnt = 2, s = 8 + 1 = 9 (divisors 1 and 8)
2. Check i = 2: 8 % 2 = 0, so 2 is a divisor
   • Increment cnt to 3, add 2 to sum: s = 9 + 2 = 11
   • Since 2 * 2 ≠ 8, we also have divisor 8 // 2 = 4
   • Increment cnt to 4, add 4 to sum: s = 11 + 4 = 15
3. Stop at i = 3 since 3 * 3 = 9 > 8
4. Final: cnt = 4, so return sum of 15

Total Result: 32 + 12 + 15 = 59

The key insight is that by checking only up to √n and handling divisor pairs together, we efficiently find all divisors while minimizing iterations.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × √m), where n is the length of the array and m represents the maximum value in the array. For each number x in the array, the helper function f(x) iterates from i = 2 to i <= x // i (which is equivalent to i <= √x), resulting in O(√x) iterations per number. Since we process all n numbers in the array, the overall time complexity is O(n × √m).

The space complexity is O(1). The algorithm only uses a constant amount of extra space for variables i, cnt, and s in the helper function, regardless of the input size. The generator expression sum(f(x) for x in nums) processes elements one at a time without storing intermediate results, maintaining constant space usage.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Initialization of Divisor Count

A common mistake is initializing the divisor count to 0 or 1 instead of 2. Since every positive integer has at least two divisors (1 and itself), we should start with divisor_count = 2. Starting from 0 would require explicitly checking for 1 and the number itself, which adds unnecessary complexity.

Wrong approach:

divisor_count = 0  # Incorrect - forgets to count 1 and n
# or
divisor_count = 1  # Incorrect - forgets to count either 1 or n

Correct approach:

divisor_count = 2  # Accounts for 1 and the number itself
divisor_sum = number + 1  # Sum includes both 1 and the number

2. Double-Counting in Perfect Square Cases

When a number is a perfect square (like 4, 9, 16), the square root is counted as a single divisor, not two. Failing to check divisor * divisor != number would count the square root twice.

Wrong approach:

if number % divisor == 0:
    divisor_count += 2  # Always adds 2 - wrong for perfect squares!
    divisor_sum += divisor + (number // divisor)

Correct approach:

if number % divisor == 0:
    divisor_count += 1
    divisor_sum += divisor
    if divisor * divisor != number:  # Only add complement if not square root
        divisor_count += 1
        divisor_sum += number // divisor

3. Loop Boundary Issues

Using divisor < number // divisor (strict inequality) instead of divisor <= number // divisor would miss the square root for perfect squares. Alternatively, iterating all the way to number-1 would be inefficient and could cause timeout for large inputs.

Wrong approaches:

# Misses square root for perfect squares
while divisor < number // divisor:  

# Inefficient - O(n) instead of O(√n)
while divisor < number:  

Correct approach:

while divisor <= number // divisor:  # Includes square root when needed

4. Starting Loop from Wrong Value

Starting the divisor check from 1 instead of 2 would duplicate the work since we already account for 1 in initialization. This doesn't break correctness but adds unnecessary iterations.

Less efficient:

divisor = 1  # Unnecessary - we already counted 1
while divisor <= number // divisor:
    if divisor == 1:  # Extra check needed
        continue

More efficient:

divisor = 2  # Start from 2 since 1 is already counted

5. Handling Edge Cases

Not properly handling small numbers (1, 2, 3) or negative numbers in the input array could lead to incorrect results. The number 1 has only one divisor (itself), and prime numbers have exactly two divisors.

Solution: The current implementation naturally handles these cases:

• Number 1: Has 1 divisor, returns 0 (correct)
• Prime numbers: Have 2 divisors, return 0 (correct)
• Numbers with exactly 4 divisors work as expected