Scale Engineer

Four Divisors

Med
#1288Time: 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.1 company
Patterns
Math
Data structures
Array
Companies
Capital One

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

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

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem