Question

1390. Four Divisors

中文文档

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 <= 104
• 1 <= 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 \times \sqrt{n})$, where $n$ is the length of the array. The space complexity is $O(1)$.

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)

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;
  }
}

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;
  }
};

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
}

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;
  };
  let ans = 0;
  for (const x of nums) {
    ans += f(x);
  }
  return ans;
}