Skip to content

Latest commit

 

History

History
60 lines (50 loc) · 1.45 KB

README.md

File metadata and controls

60 lines (50 loc) · 1.45 KB

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.

// OJ: https://leetcode.com/problems/four-divisors/
// Author: github.com/lzl124631x
// 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;
    }
};