1390. Four Divisors

Source: Dev.to

Problem Statement

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.

Examples

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

Only 21 qualifies, and the sum of its divisors is 1 + 3 + 7 + 21 = 32.

Example 2

Input: nums = [21,21]
Output: 64

Both elements are 21, each contributing 32 to the total.

Example 3

Input: nums = [1,2,3,4,5]
Output: 0

No number in the array has exactly four divisors.

Constraints

1  4) {
                // More than four divisors – not eligible.
                return 0;
            }
        }
    }

    return ($cnt === 4) ? $sum : 0;
}

// Test cases
echo sumFourDivisors([21,4,7]) . "\n";          // Output: 32
echo sumFourDivisors([21,21]) . "\n";           // Output: 64
echo sumFourDivisors([1,2,3,4,5]) . "\n";       // Output: 0
?>

Solution (PHP)

<?php
function sumFourDivisors(array $nums): int {
    $total = 0;
    foreach ($nums as $num) {
        $total += fourDivisorsSum($num);
    }
    return $total;
}

function fourDivisorsSum(int $n): int {
    $cnt = 0;
    $sum = 0;
    for ($i = 1; $i * $i <= $n; $i++) {
        if ($n % $i === 0) {
            $cnt++;
            $sum += $i;
            $other = intdiv($n, $i);
            if ($other !== $i) {
                $cnt++;
                $sum += $other;
            }
            if ($cnt > 4) {
                // More than four divisors – not eligible.
                return 0;
            }
        }
    }

    return ($cnt === 4) ? $sum : 0;
}

// Test cases
echo sumFourDivisors([21,4,7]) . "\n";          // Output: 32
echo sumFourDivisors([21,21]) . "\n";           // Output: 64
echo sumFourDivisors([1,2,3,4,5]) . "\n";       // Output: 0
?>

Main Algorithm

1. Iterate over each element of the input array.
2. Determine whether the current number has exactly four divisors by scanning up to its square root, counting and summing divisors on the fly.
3. Accumulate the sum for numbers that meet the condition.

Complexity Analysis

• Time Complexity: O(n × √m), where n is the length of nums and m is the maximum value in nums.
• Space Complexity: O(1) auxiliary space (excluding the input array).