Four Divisors

medium array math number theory

Problem

Given an integer array nums, return the sum of divisors of the integers that have exactly four divisors. If no integer in the array has exactly four divisors, return 0.

Inputnums = [21, 4, 7]

Output32

21 has divisors 1, 3, 7, 21 (exactly four), summing to 32. 4 has three divisors and 7 has two, so only 21 contributes.

Inputnums = [1, 2, 3, 4, 5]

Output0

None of these has exactly four divisors.

nums (comma-separated)

def sumFourDivisors(nums):
    total = 0
    for n in nums:
        cnt, dsum = 2, 1 + n
        i = 2
        while i * i <= n:
            if n % i == 0:
                cnt += 1
                dsum += i
                if i != n // i:
                    cnt += 1
                    dsum += n // i
                if cnt > 4:
                    break
            i += 1
        if cnt == 4:
            total += dsum
    return total

function sumFourDivisors(nums) {
  let total = 0;
  for (const n of nums) {
    let cnt = 2, dsum = 1 + n;
    for (let i = 2; i * i <= n; i++) {
      if (n % i === 0) {
        cnt++; dsum += i;
        if (i !== Math.floor(n / i)) {
          cnt++; dsum += Math.floor(n / i);
        }
        if (cnt > 4) break;
      }
    }
    if (cnt === 4) total += dsum;
  }
  return total;
}

int sumFourDivisors(int[] nums) {
    int total = 0;
    for (int n : nums) {
        int cnt = 2, dsum = 1 + n;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                cnt++; dsum += i;
                if (i != n / i) {
                    cnt++; dsum += n / i;
                }
                if (cnt > 4) break;
            }
        }
        if (cnt == 4) total += dsum;
    }
    return total;
}

int sumFourDivisors(vector<int>& nums) {
    int total = 0;
    for (int n : nums) {
        int cnt = 2, dsum = 1 + n;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                cnt++; dsum += i;
                if (i != n / i) {
                    cnt++; dsum += n / i;
                }
                if (cnt > 4) break;
            }
        }
        if (cnt == 4) total += dsum;
    }
    return total;
}

Explanation

We treat each number independently and ask one question: does it have exactly four divisors? If so, we add the sum of those divisors to a running total.

To count divisors of n we use trial division up to √n. Every divisor i below √n is paired with a matching divisor n / i above it, so we only need to scan i from 2 to √n and count both members of each pair. We seed the counters with the two divisors that always exist, 1 and n (so cnt = 2 and dsum = 1 + n).

When i divides n we add i, and if its partner n / i is different (it is equal only for a perfect-square divisor), we add that too. The moment cnt exceeds 4 we can break early: this number can never qualify.

After the scan, a number contributes only when cnt == 4. Numbers with exactly four divisors are precisely those of the form p · q (two distinct primes) or p³ (a prime cubed); the trial-division count handles both cases without special-casing.

For nums = [21, 4, 7]: 21 = 3·7 has divisors {1, 3, 7, 21} → contributes 32; 4 has {1, 2, 4} (three); 7 has {1, 7} (two). The answer is 32.

Time: O(n · √m) Space: O(1)