# Four Divisors
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/four-divisors)
Canonical: https://scaleengineer.com/dsa/problems/four-divisors
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
**Companies:** [Capital One](https://scaleengineer.com/companies/capital-one)
---
## Problem
Given an integer array `nums`, return _the sum of divisors of the integers in that array that have exactly four divisors_. If there is no such integer in the array, return `0`.

**Example 1:**

**Input:** nums = [21,4,7]
**Output:** 32
**Explanation:** 
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 3:**

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

**Constraints:**

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

# Approaches
## Brute-Force Trial Division
This is the most straightforward approach. For each number in the input array, we iterate from 1 up to the number itself to find all its divisors. We count them and sum them up. If the count is exactly four, we add this sum to our total result.
**Time:** O(N * M), where `N` is the length of `nums` and `M` is the maximum value in `nums`. For each of the `N` numbers, we iterate up to `M`. This is too slow given the constraints (`10^4 * 10^5 = 10^9`) and will result in a Time Limit Exceeded error. · **Space:** O(1), as we only use a few variables to store the sums and counts.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient and will not pass the time limits for the given constraints.
### Explanation
This is the most intuitive but least efficient solution. The idea is to directly translate the problem statement into code. For every number in the input array, we check every possible divisor from 1 up to the number itself.

The algorithm works as follows:

*   Initialize a variable `totalSum` to 0.
*   Loop through each number `num` in the input array `nums`.
*   For each `num`, we need to find its properties. So, we initialize two temporary variables: `divisorCount = 0` and `currentSum = 0`.
*   We start another loop with a counter `i` from 1 up to `num`.
*   Inside this inner loop, we check if `i` is a divisor of `num` using the modulo operator (`num % i == 0`).
*   If `i` is a divisor, we increment `divisorCount` and add the value of `i` to `currentSum`.
*   Once the inner loop completes (we have checked all numbers from 1 to `num`), we examine the `divisorCount`.
*   If `divisorCount` is exactly 4, it means `num` meets the condition. We then add its `currentSum` to the `totalSum`.
*   After the outer loop finishes processing all numbers in `nums`, the `totalSum` will hold the final answer, which we return.

This method is simple to conceptualize but its performance is poor for large inputs.
```java
class Solution {
    public int sumFourDivisors(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            int divisorCount = 0;
            int currentSum = 0;
            // Iterate from 1 to num to find all divisors
            for (int i = 1; i <= num; i++) {
                if (num % i == 0) {
                    divisorCount++;
                    currentSum += i;
                }
            }
            // Check if the count of divisors is exactly 4
            if (divisorCount == 4) {
                totalSum += currentSum;
            }
        }
        return totalSum;
    }
}
```
### Algorithm
*   Initialize a variable `totalSum` to 0.
*   Iterate through each number `num` in the input array `nums`.
*   For each `num`, initialize `divisorCount = 0` and `currentSum = 0`.
*   Start a loop with a counter `i` from 1 to `num`.
*   Inside the loop, check if `i` is a divisor of `num` (i.e., `num % i == 0`).
*   If it is, increment `divisorCount` and add `i` to `currentSum`.
*   After the inner loop finishes, check if `divisorCount` is equal to 4.
*   If it is, add `currentSum` to `totalSum`.
*   After iterating through all numbers in `nums`, return `totalSum`.

## Optimized Trial Division
This approach improves upon the brute-force method by optimizing how we find divisors. Instead of iterating up to the number `num`, we only need to iterate up to its square root. If `i` is a divisor, then `num / i` is also a divisor. This significantly reduces the number of checks needed for each number.
**Time:** O(N * sqrt(M)), where `N` is the length of `nums` and `M` is the maximum value in `nums`. For each of the `N` numbers, we iterate up to `sqrt(M)`. With `N=10^4` and `M=10^5`, this is roughly `10^4 * 316`, which is acceptable. · **Space:** O(1), as we only use a few variables per number.
**Pros:** Significantly faster than the naive brute-force approach.; Easy to implement and requires no extra space.
**Cons:** Can be slower than pre-computation methods if `N` is very large or if the same numbers are processed repeatedly.
### Explanation
The core idea is to reduce the search space for divisors. For any integer `num`, if `i` is a divisor, then `num / i` is also a divisor. We only need to iterate from 1 up to the integer part of `sqrt(num)`.

The algorithm proceeds as follows:

*   Initialize a variable `totalSum` to 0, which will store the final result.
*   Iterate through each number `num` in the input array `nums`.
*   For each `num`, we need to find its divisors, count them, and calculate their sum. We initialize `divisorCount = 0` and `currentSum = 0`.
*   We loop with a counter `i` from 1 up to `sqrt(num)`.
*   In each iteration, we check if `i` divides `num` evenly (`num % i == 0`).
    *   If it does, we have found at least one divisor.
    *   We must handle the case where `num` is a perfect square. If `i * i == num`, then `i` and `num / i` are the same. We count this as one divisor and add `i` to `currentSum`.
    *   Otherwise (`i * i != num`), we have found two distinct divisors: `i` and `num / i`. We count these as two divisors and add both `i` and `num / i` to `currentSum`.
*   After the loop finishes for a given `num`, we check if `divisorCount` is exactly 4.
*   If it is, we add the `currentSum` for this `num` to our `totalSum`.
*   After processing all numbers in `nums`, `totalSum` holds the required result.

Here is the implementation in Java:
```java
class Solution {
    public int sumFourDivisors(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            int count = 0;
            int currentSum = 0;

            // Iterate up to the square root of num
            for (int i = 1; i * i <= num; i++) {
                if (num % i == 0) {
                    // i is a divisor
                    if (i * i == num) {
                        // Perfect square case, one divisor
                        count++;
                        currentSum += i;
                    } else {
                        // Two distinct divisors: i and num/i
                        count += 2;
                        currentSum += i + (num / i);
                    }
                }
            }

            // If the number has exactly four divisors, add their sum to the total
            if (count == 4) {
                totalSum += currentSum;
            }
        }
        return totalSum;
    }
}
```
### Algorithm
*   Initialize `totalSum` to 0.
*   Iterate through each number `num` in `nums`.
*   For each `num`, initialize `divisorCount = 0` and `currentSum = 0`.
*   Iterate `i` from 1 up to `sqrt(num)`.
*   If `i` divides `num`:
    *   If `i * i == num`, we found one divisor `i`. Increment `divisorCount` by 1 and add `i` to `currentSum`.
    *   If `i * i != num`, we found two divisors, `i` and `num / i`. Increment `divisorCount` by 2 and add `i + num / i` to `currentSum`.
*   After the loop, if `divisorCount` is 4, add `currentSum` to `totalSum`.
*   Return `totalSum`.

## Sieve-based Pre-computation
Since the maximum value of a number in the array is limited (`10^5`), we can pre-compute the number of divisors and the sum of divisors for all integers up to this limit. This is done using a sieve-like algorithm. After the one-time pre-computation, we can answer the query for each number in the input array in constant time.
**Time:** O(M * log(M) + N), where `M` is the maximum value in `nums` and `N` is the length of `nums`. The pre-computation step takes `O(M * log(M))` time. The final loop to sum up the results takes `O(N)`. This is the most efficient approach for the given constraints. · **Space:** O(M) to store the `divisorCount` and `divisorSum` arrays, where `M` is the maximum value in `nums`.
**Pros:** Very fast due to pre-computation.; Each query after the initial setup is O(1).
**Cons:** Requires extra space proportional to the maximum value in the input array.
### Explanation
This approach leverages pre-computation to solve the problem efficiently, especially when the range of numbers is fixed and relatively small. The constraint `nums[i] <= 10^5` makes this a viable strategy. We can pre-calculate the number of divisors and the sum of divisors for every number up to the maximum possible value in the input array.

The algorithm is as follows:

*   First, determine the maximum value `maxVal` present in the `nums` array. This sets the upper bound for our pre-computation.
*   Create two integer arrays, `divisorCount` and `divisorSum`, both of size `maxVal + 1`. `divisorCount[k]` will store the number of divisors of `k`, and `divisorSum[k]` will store the sum of divisors of `k`.
*   Populate these arrays using a method similar to the Sieve of Eratosthenes.
    *   Iterate with a variable `i` from 1 to `maxVal`. This `i` represents a potential divisor.
    *   For each `i`, iterate through its multiples `j` (i.e., `j = i, 2*i, 3*i, ...`) up to `maxVal`.
    *   For each multiple `j`, we know that `i` is a divisor. So, we increment `divisorCount[j]` and add `i` to `divisorSum[j]`.
*   After the pre-computation is complete, initialize `totalSum = 0`.
*   Iterate through each `num` in the input array `nums`.
*   For each `num`, we can now perform an `O(1)` lookup. If `divisorCount[num]` is equal to 4, it means `num` has exactly four divisors. In this case, we add the pre-computed `divisorSum[num]` to our `totalSum`.
*   Finally, return the `totalSum`.

Here is the Java implementation:
```java
class Solution {
    public int sumFourDivisors(int[] nums) {
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        int[] divisorCount = new int[maxVal + 1];
        int[] divisorSum = new int[maxVal + 1];

        // Sieve to pre-compute divisor counts and sums
        for (int i = 1; i <= maxVal; i++) {
            for (int j = i; j <= maxVal; j += i) {
                divisorCount[j]++;
                divisorSum[j] += i;
            }
        }

        int totalSum = 0;
        // Process the input array using pre-computed values
        for (int num : nums) {
            if (num <= maxVal && divisorCount[num] == 4) {
                totalSum += divisorSum[num];
            }
        }
        return totalSum;
    }
}
```
### Algorithm
*   Find the maximum value `max_val` in the `nums` array.
*   Create two arrays, `divisorCount` and `divisorSum`, of size `max_val + 1`.
*   Populate these arrays using a sieve method:
    *   Iterate `i` from 1 to `max_val`.
    *   For each `i`, iterate through its multiples `j = i, 2*i, 3*i, ...` up to `max_val`.
    *   For each multiple `j`, `i` is a divisor. So, increment `divisorCount[j]` and add `i` to `divisorSum[j]`.
*   Initialize `totalSum` to 0.
*   Iterate through each `num` in the input array `nums`.
*   Look up `divisorCount[num]`. If it is 4, add `divisorSum[num]` to `totalSum`.
*   Return `totalSum`.

# Solutions
### Java

```java
class Solution { public int sumFourDivisors ( int [] nums ) { int ans = 0 ; for ( int x : nums ) { ans += f ( x ); } return ans ; } private int f ( int x ) { int cnt = 2 , s = x + 1 ; for ( int i = 2 ; i <= x / i ; ++ i ) { if ( x % i == 0 ) { ++ cnt ; s += i ; if ( i * i != x ) { ++ cnt ; s += x / i ; } } } return cnt == 4 ? s : 0 ; } }
```

### CPP

```cpp
class Solution { public: int sumFourDivisors ( vector < int >& nums ) { int ans = 0 ; for ( int x : nums ) { ans += f ( x ); } return ans ; } int f ( int x ) { int cnt = 2 , s = x + 1 ; for ( int i = 2 ; i <= x / i ; ++ i ) { if ( x % i == 0 ) { ++ cnt ; s += i ; if ( i * i != x ) { ++ cnt ; s += x / i ; } } } return cnt == 4 ? s : 0 ; } };
```

### Python

```python
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 )
```