#1390

Medium

LeetCode Problem Workspace

Four Divisors

Compute the sum of all divisors for numbers in an array that have exactly four divisors using array and math techniques.

array math

Problem Statement

Given an integer array nums, calculate the sum of all divisors of numbers that have exactly four divisors. If a number does not have exactly four divisors, it should be ignored. Return the total sum across all qualifying numbers in the array.

For example, given nums = [21,4,7], 21 has divisors 1,3,7,21 (exactly four), 4 has divisors 1,2,4 (three divisors), and 7 has divisors 1,7 (two divisors). The sum of divisors for qualifying numbers is 32. Constraints: 1 <= nums.length <= 104 and 1 <= nums[i] <= 105.

Examples

Example 1

Input: nums = [21,4,7]

Output: 32

21 has 4 divisors: 1, 3, 7, 21 4 has 3 divisors: 1, 2, 4 7 has 2 divisors: 1, 7 The answer is the sum of divisors of 21 only.

Example 2

Input: nums = [21,21]

Output: 64

Example details omitted.

Example 3

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

Output: 0

Example details omitted.

Constraints

1 <= nums.length <= 104
1 <= nums[i] <= 105

Solution Approach

Brute-Force Divisor Count

Iterate through each number in nums and count all divisors by checking each integer up to its square root. Sum the divisors if exactly four divisors are found. This approach is simple but can be slow for large arrays due to O(n*sqrt(max_num)) time.

Mathematical Pattern Optimization

Recognize that numbers with exactly four divisors are either cubes of primes or products of two distinct primes. Use this property to check numbers efficiently without counting all divisors explicitly. This reduces redundant divisor checks and improves performance.

Array Traversal with Early Termination

Traverse nums while applying the divisor pattern check. For each number, stop further checking once more than four divisors are found. Accumulate the sum only for valid numbers. This combines array iteration with mathematical pruning for better efficiency.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity varies by method: brute-force is O(n sqrt(m)) for array size n and max element m, while pattern-based checking can approach O(n log m). Space complexity is O(1) beyond input storage, as no extra arrays are needed.

What Interviewers Usually Probe

Looking for recognition that exactly four divisors have a prime-product pattern.
Expect early termination once a number exceeds four divisors.
Interest in distinguishing brute-force versus optimized math approaches.

Common Pitfalls or Variants

Common pitfalls

Assuming all numbers need full divisor enumeration without pruning.
Forgetting that numbers can repeat and each instance contributes to the sum.
Counting numbers with fewer or more than four divisors by mistake.

Follow-up variants

Count numbers with exactly three divisors instead of four.
Return only the sum of numbers themselves, not their divisors.
Apply the problem to a 2D array where each row is treated as nums.

FAQ

How do I identify numbers with exactly four divisors efficiently?

Check if a number is either a product of two distinct primes or a cube of a prime, which guarantees exactly four divisors.

Does the solution handle repeated numbers in the array?

Yes, each occurrence of a number with four divisors contributes to the sum independently.

What is the maximum divisor check needed for numbers in nums?

Only check up to the square root of each number; paired divisors account for the rest.

Can this problem be solved without checking all divisors?

Yes, using the mathematical pattern for numbers with exactly four divisors avoids full enumeration.

Why is this considered an Array plus Math problem?

Because it combines array traversal with mathematical recognition of divisor patterns to compute sums efficiently.

terminal

Solution

Solution 1: Factor Decomposition

We can perform factor decomposition on each number. If the number of factors is $4$, then this number meets the requirements of the problem, and we can add its factors to the answer.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def sumFourDivisors(self, nums: List[int]) -> int:
        def f(x: int) -> int:
            i = 2
            cnt, s = 2, x + 1
            while i <= x // i:
                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)

Continue Practicing

#1406 stone game iii #1363 largest multiple of three #1352 product of the last k numbers