Problem overview
The method perfectNumbers receives a list of integers nums and returns the perfect numbers among them, in the same order. A number is perfect when it equals the sum of its divisors that are smaller than itself. For example, 6 is perfect, because 1 + 2 + 3 = 6. The number 1 is not perfect: it has no smaller divisors, so its sum is 0. A perfect number that appears twice is kept twice, and the result is empty if none qualifies.
For [6, 8, 28, 12] the answer is [6, 28]. For [1, 5, 10] it is []. For [496, 6, 6] it is [496, 6, 6]. The numbers are between 1 and 10,000, and there are at most 20.
Approach: a helper for the divisor sum
The work is split in two. The helper sumOfDivisors returns the sum of the divisors of one number that are smaller than it. perfectNumbers then keeps each number that equals its own helper result.
The helper tries every candidate from 1 up to n - 1. A candidate d is a divisor when n % d == 0, meaning the division leaves no remainder. The sums for the examples are:
| n | sum of smaller divisors | perfect? |
|---|---|---|
| 1 | 0 | no |
| 5 | 1 | no |
| 6 | 6 | yes |
| 8 | 7 | no |
| 10 | 8 | no |
| 12 | 16 | no |
Step by step
- In
sumOfDivisors, starttotal = 0. - Loop with
for d in range(1, n): 1 up ton - 1. The end of a range is excluded, sonitself is left out, as the task needs. - If
n % d == 0, adddtototal. - Return
total. - In
perfectNumbers, start with an empty listperfect. - Loop with
for num in nums. Ifself.sumOfDivisors(num) == num, appendnum. - Return
perfect.
The solution in Python
class Solution:
def sumOfDivisors(self, n: int) -> int:
total = 0
for d in range(1, n):
if n % d == 0:
total += d
return total
def perfectNumbers(self, nums: List[int]) -> List[int]:
perfect = []
for num in nums:
if self.sumOfDivisors(num) == num:
perfect.append(num)
return perfectDetails:
- For
n = 1,range(1, 1)is empty, so the sum stays 0 and 1 is correctly not perfect. - For 28 the divisors found are 1, 2, 4, 7 and 14, which add up to 28.
- For 496 the loop finds 1, 2, 4, 8, 16, 31, 62, 124 and 248, which also add up to 496.
- Repeated numbers are visited every time, so a repeated perfect number is kept every time.
Why a helper
Finding the divisor sum is a job of its own with its own loop and its own total. Putting it in sumOfDivisors means perfectNumbers does not need a loop inside a loop. Its body is one comparison, and the helper can be checked alone: sumOfDivisors(6) is 6, sumOfDivisors(8) is 7 and sumOfDivisors(1) is 0.
Cost
The helper runs about n turns for each number, and the largest number is 10,000. With at most 20 numbers, that is about 200,000 checks in the worst case, which is very fast. Nothing cleverer is needed.
Testing
| nums | result |
|---|---|
[6, 8, 28, 12] | [6, 28] |
[1, 5, 10] | [] |
[496, 6, 6] | [496, 6, 6] |
Common mistakes
- Using
range(1, n + 1). The number itself would be included: for 6 the sum becomes 12, and nothing is ever perfect. - Using
range(n). It starts at 0, andn % 0raisesZeroDivisionError. - Writing
n / d == 0. A divisor is found with the remainder%, not the quotient. - Returning inside the loop. The helper would stop after the first divisor.
- Forgetting
self.when calling the helper from the other method.
