Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Divisors occur in pairs: if d divides x, then x / d does too. At least one member of every pair is at most the square root, so scanning only that range finds every divisor. A set avoids counting a square root twice.

Approach

For each input value, test candidate divisors from one through its integer square root and insert both members of every divisor pair into a set. Stop early once the set contains more than four values, since further discoveries cannot restore eligibility. Add the set's sum only if its final size is exactly four. Accumulate separately for every input occurrence.

class Solution:
    def sumFourDivisors(self, nums: List[int]) -> int:
        res = 0

        for x in nums:
            div = set()
            for d in range(1, floor(sqrt(x)) + 1):
                if x % d == 0:
                    div.add(x // d)
                    div.add(d)
                if len(div) > 4:
                    break
            if len(div) == 4:
                res += sum(div)

        return res

Complexity analysis

For each value x, trial division runs through at most floor(sqrt(x)), so total time is O(Σ sqrt(x)) over all inputs. The divisor set is stopped once it exceeds four elements, so auxiliary space is O(1).