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 <= 1041 <= nums[i] <= 105
Solutions
Solution 1: Factor Decomposition
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 × √n), where n is the length of the array. The space complexity is O(1).
PythonJavaC++GoTypeScriptRust
class Solution:
def sumFourDivisors(self, nums: List[int]) -> int:
def f(x: int) -> int:
i = 2
cnt, s = 2, x + 1
while i <= x // i:
if x % i == 0:
cnt += 1
s += i
if i * i != x:
cnt += 1
s += x // i
i += 1
return s if cnt == 4 else 0
return sum(f(x) for x in nums)(code-box)
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;
}
}(code-box)
class Solution {
public:
int sumFourDivisors(vector<int>& nums) {
int ans = 0;
for (int x : nums) {
ans += f(x);
}
return ans;
}
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;
}
};(code-box)
func sumFourDivisors(nums []int) (ans int) {
f := func(x int) int {
cnt, s := 2, x+1
for i := 2; i <= x/i; i++ {
if x%i == 0 {
cnt++
s += i
if i*i != x {
cnt++
s += x / i
}
}
}
if cnt == 4 {
return s
}
return 0
}
for _, x := range nums {
ans += f(x)
}
return
}(code-box)
function sumFourDivisors(nums: number[]): number {
const f = (x: number): number => {
let cnt = 2;
let s = x + 1;
for (let i = 2; i * i <= x; ++i) {
if (x % i === 0) {
++cnt;
s += i;
if (i * i !== x) {
++cnt;
s += Math.floor(x / i);
}
}
}
return cnt === 4 ? s : 0;
};
return nums.reduce((acc, x) => acc + f(x), 0);
}(code-box)
impl Solution {
pub fn sum_four_divisors(nums: Vec<i32>) -> i32 {
let f = |x: i32| -> i32 {
let mut cnt = 2;
let mut s = x + 1;
let mut i = 2;
while i <= x / i {
if x % i == 0 {
cnt += 1;
s += i;
if i * i != x {
cnt += 1;
s += x / i;
}
}
i += 1;
}
if cnt == 4 { s } else { 0 }
};
let mut ans = 0;
for x in nums {
ans += f(x);
}
ans
}
}(code-box)
