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 <= 1041 <= nums[i] <= 105Problem Overview: You receive an integer array nums. For each number, determine whether it has exactly four divisors. If it does, add the sum of those divisors to the final result. Return the total across all numbers.
Approach 1: Naive Divisor Counting (O(n * √m) time, O(1) space)
For every number in nums, iterate from 1 to √num and check whether the current value divides the number. When a divisor d is found, add both d and num / d to the divisor set (handling the square root case carefully). Count how many divisors appear and compute their sum. If the total divisor count equals exactly four, include the sum in the final answer. This approach directly simulates divisor enumeration using basic math operations and simple iteration over the array.
Approach 2: Optimized Divisor Checking (O(n * √m) time, O(1) space)
Instead of collecting every divisor, track the count while scanning up to √num. Each time a divisor is found, increment the count by two (for the pair d and num/d) and add them to the running sum. The key optimization: stop early once the divisor count exceeds four. Most numbers have more than four divisors, so early termination avoids unnecessary checks. For numbers that end with exactly four divisors, the accumulated sum is added to the result. This keeps memory constant while reducing wasted work during divisor scans.
Recommended for interviews: The optimized divisor checking approach is typically expected. Interviewers want to see that you limit the search to √num and prune early when the divisor count exceeds four. Showing the naive enumeration first demonstrates understanding of divisor properties, but the optimized version proves you can reduce unnecessary computation in real coding interviews.
This approach involves iterating over each integer in the input array nums. For each integer, we count its divisors by checking every number from 1 up to the integer itself. If a number has exactly four divisors, we add the sum of these divisors to our total sum.
This C code defines a function sumFourDivisors that iterates over each integer in the given array. For each integer, it calculates the number and sum of its divisors. If exactly four divisors are found, their sum is added to the final result.
Time Complexity: O(n * m), where n is the length of the input array and m is the maximum integer value in the array (at most 100,000).
Space Complexity: O(1), as no extra space is used beyond primitive variables.
This solution optimizes the divisor counting by iterating only up to the square root of each number. This reduces redundant calculations since divisors come in pairs. When exactly four divisors are found, their sum is included in the result.
This C implementation checks divisors up to the square root of each number, leveraging divisor pairs to minimize redundant calculations. This optimized approach efficiently determines and sums exactly four divisors if they exist.
Time Complexity: O(n * √m), reducing each number's divisor checks to its square root.
Space Complexity: O(1).
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.
The time complexity is O(n times \sqrt{n}), where n is the length of the array. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Naive Divisor Counting | Time Complexity: O(n * m), where n is the length of the input array and m is the maximum integer value in the array (at most 100,000). |
| Optimized Divisor Checking | Time Complexity: O(n * √m), reducing each number's divisor checks to its square root. |
| Factor Decomposition | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Divisor Counting | O(n * √m) | O(1) | Simple implementation when constraints are small or clarity matters more than pruning |
| Optimized Divisor Checking (Early Stop) | O(n * √m) | O(1) | Preferred in interviews; stops scanning once divisor count exceeds four |
Four Divisors | Simplest Explanation | Dry Run | Straight Forward | Leetcode 1390 | codestorywithMIK • codestorywithMIK • 8,859 views views
Watch 9 more video solutions →Practice Four Divisors with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor