Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1390.html
1390. Four Divisors (Medium)
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
Related Topics:
Math
Solution 1.
-
class Solution { public int sumFourDivisors(int[] nums) { int sum = 0; for (int num : nums) sum += sumFourDivisors(num); return sum; } public int sumFourDivisors(int num) { if (num <= 5) return 0; if (isPrime(num)) return 0; int sqrt = (int) Math.sqrt(num); int prime1 = 0, remain = 0; if (num % 2 == 0) { prime1 = 2; remain = num / 2; } else { for (int i = 3; i <= sqrt; i += 2) { if (num % i == 0) { prime1 = i; remain = num / i; break; } } } if (prime1 > 0 && remain == prime1 * prime1 || remain > prime1 && isPrime(remain)) return 1 + prime1 + remain + num; else return 0; } public boolean isPrime(int num) { if (num == 1) return false; if (num == 2 || num == 3) return true; if (num % 2 == 0 || num % 3 == 0) return false; int sqrt = (int) Math.sqrt(num); for (int i = 5; i <= sqrt; i += 2) { if (num % i == 0) return false; } return true; } }
-
// OJ: https://leetcode.com/problems/four-divisors/ // Time: O(N) // Space: O(1) class Solution { public: int sumFourDivisors(vector<int>& nums) { int ans = 0; for (int n : nums) { int cnt = 0, sum = 0; for (int i = 1; i * i <= n && cnt <= 4; ++i) { if (n % i) continue; int j = n / i; ++cnt; sum += i; if (i != j) { ++cnt; sum += j; } } if (cnt != 4) continue; ans += sum; } return ans; } };