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.
Constraints:
1 <= nums.length <= 10^4
1 <= nums[i] <= 10^5
Solution: Math
If a number is a perfect square (e.g. 9 = 3 * 3), it will have odd number of divisors. (9: 1, 3, 9).
Time complexity: O(sum(sqrt(num_i))
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: int sumFourDivisors(vector<int>& nums) { int ans = 0; for (int n : nums) { int r = sqrt(n); if (n <= 4 || r * r == n) continue; int count = 2; int sum = 1 + n; for (int d = 2; d <= r; ++d) if (n % d == 0) { count += 2; sum += n / d + d; } if (count == 4) ans += sum; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment