Four Divisors

MEDIUM

Description

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 <= 10⁴
1 <= nums[i] <= 10⁵

Approaches

Checkout 3 different approaches to solve Four Divisors. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1), as we only use a few variables to store the sums and counts.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Extremely inefficient and will not pass the time limits for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Four Divisors. Click on different languages to view the code.

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 ; } }

Video Solution

Watch the video walkthrough for Four Divisors

Patterns:

Math

Data Structures:

Array

Companies:

Capital One |