Problem overview
perfectNumbers receives a slice 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.
For [6, 8, 28, 12] the answer is [6 28]. The sum for 8 is 1 + 2 + 4 = 7, and for 12 it is 1 + 2 + 3 + 4 + 6 = 16. For [1, 5, 10] nothing qualifies, so the result is empty. For [496, 6, 6] all three are perfect.
Approach
Again the work is split. The helper sumOfDivisors computes the sum for one number, and perfectNumbers keeps every number that equals the sum the helper gives for it. The rule of the problem is then a single comparison in the loop.
With numbers up to 10,000 and at most 20 of them, trying every candidate divisor from 1 up to n - 1 is fast enough, so the helper stays simple.
Step by step
The helper sumOfDivisors(n):
- Start
total := 0. Forn = 1the loop never runs, so the sum stays 0. - Loop with
dfrom 1 whiled < n. Stopping beforenleaves out the number itself. - If
n % d == 0, a remainder of 0 meansddividesn, so adddtototal. - Return
total.
The function perfectNumbers(nums):
- Create
perfect := []int{}. - Loop with
for _, num := range nums. - If
sumOfDivisors(num) == num, appendnumand assign the slice back toperfect. A repeated perfect number is visited twice, so it is kept twice. - Return
perfectafter the loop. If nothing matched, it is still the empty slice, which is the right answer.
The solution in Go
func sumOfDivisors(n int) int {
total := 0
for d := 1; d < n; d++ {
if n % d == 0 {
total += d
}
}
return total
}
func perfectNumbers(nums []int) []int {
perfect := []int{}
for _, num := range nums {
if sumOfDivisors(num) == num {
perfect = append(perfect, num)
}
}
return perfect
}
The loop variable d is declared in the for statement with := and exists only inside the loop. Go has no parentheses around the loop header.
What the helper computes
For 6, the loop tries d from 1 to 5. The remainder is 0 for 1, 2 and 3 and nonzero for 4 and 5, so the helper adds 1 + 2 + 3 and returns 6, which equals the number. For 8 it adds 1, 2 and 4 and returns 7, which is not 8. For 1 the loop does not run at all, because d starts at 1 and the condition d < 1 is false from the start. The helper returns 0, and 0 does not equal 1.
Why a helper
The definition of a perfect number has two parts: add up the smaller divisors, then compare with the number. The helper does the first part and the main function does the second. Each part is a few lines and can be understood without the other.
Speed
The helper does about n steps for a number n, and the main function calls it once per number. With at most 20 numbers of at most 10,000 each, that is about 200,000 steps, which is instant. There are faster ways to list divisors, but they would add complexity the lesson does not need.
Perfect numbers are rare
Among the numbers from 1 to 10,000 only 6, 28, 496 and 8128 are perfect. Most tests will therefore return an empty slice or a short one.
The helper can also be called on its own. sumOfDivisors(28) is 28 and sumOfDivisors(496) is 496, so both are perfect. sumOfDivisors(2) and sumOfDivisors(5) are both 1, because the only smaller divisor of a prime number is 1. sumOfDivisors(10) is 8, as in the statement's second example.
Testing
[6 8 28 12] -> [6 28]
[1 5 10] -> []
[496 6 6] -> [496 6 6]
sumOfDivisors(8) -> 7
sumOfDivisors(12) -> 16
sumOfDivisors(1) -> 0
Edge cases
The filter has the same shape as any "keep the ones that pass" loop: visit each element, ask a yes-or-no question, append when the answer is yes. That is why order and duplicates come out right with no extra work, since the loop visits the elements in order, one by one. The smallest allowed number, 1, is handled by the helper returning 0 without running its loop, and the result for a slice with no perfect number is the empty slice that perfect started as.
Common mistakes
- Using
d <= n. That addsnitself, so every number's sum is at leastnand the sums become wrong (6 would give 12). - Starting
dat 0.n % 0is a division by zero and panics at run time. - Treating 1 as perfect. Its sum is 0, not 1, and the loop correctly gives 0.
- Removing duplicates. The statement keeps a perfect number every time it appears.
