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] <= 105This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * √m), reducing each number's divisor checks to its square root.
Space Complexity: 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. |
4 Leetcode Mistakes • Sahil & Sarra • 421,889 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