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.

• Java
• C++

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

All Problems

All Solutions