Problem Statement in English

You’re given an integer array nums. For each nums[i], you need to find the sum of its divisors if it has exactly four divisors.

If it does not have exactly four divisors, you should ignore that number.

Approach

You basically just need to do what the question asks.

Just to optimize a bit, we can note that divisors come in pairs. So if d is a divisor of n, then n / d is also a divisor of n.

Further, we only need to visit divisors up to $\sqrt{n}$, because any divisor larger than that would have already been paired with a smaller divisor.

And we’re done.

Solution in Python


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

        for num in nums:
            cnt = 0
            total = 0

            for d in range(1, isqrt(num) + 1):
                if num % d == 0:
                    cnt += 1
                    total += d

                    other = num // d
                    if other != d:
                        cnt += 1
                        total += other

                if cnt > 4:
                    break

            if cnt == 4:
                res += total

        return res

Complexity

  • Time: $O(n \sqrt{m})$
    Where n is the length of nums and m is the maximum number in nums.

  • Space: $O(1)$
    We are using only a constant amount of extra space.

And we are done.