Problem overview
The function perfectNumbers receives an array 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 6 the smaller divisors are 1, 2 and 3, and 1 + 2 + 3 = 6, so 6 is perfect. 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 if none is perfect the result is empty.
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] the answer is [], since the sums are 0, 1 and 8. For [496, 6, 6] the answer is [496, 6, 6].
Approach: a helper for the sum
The lesson splits the job in two. The helper sumOfDivisors returns the sum of the divisors of n that are smaller than n. perfectNumbers keeps each number that equals the helper's answer for it.
To find the divisors, try every number d from 1 up to n - 1. A number d divides n evenly when the remainder n % d is 0. Each such d is added to a running total. With n at most 10,000 and at most 20 numbers, trying every candidate is fast enough.
Step by step
- Start the total with
var total = 0. - Loop over the candidates:
for d in 1..<n. The half-open range stops atn - 1, sonitself is left out. Forn = 1the range is empty and the total stays 0. - Test each one: if
n % d == 0, adddtototal. - Return
total. - In
perfectNumbers, start with an empty array,var perfect = [Int](). - Loop over
nums. A perfect number that appears twice is visited twice, so it is kept twice. - Append
numwhensumOfDivisors(num) == num. - Return
perfect, which stays empty if nothing matched.
The solution in Swift
class Solution {
func sumOfDivisors(_ n: Int) -> Int {
var total = 0
for d in 1..<n {
if n % d == 0 {
total += d
}
}
return total
}
func perfectNumbers(_ nums: [Int]) -> [Int] {
var perfect = [Int]()
for num in nums {
if sumOfDivisors(num) == num {
perfect.append(num)
}
}
return perfect
}
}
Swift details: the range 1..<n is only valid when n is at least 1. Swift stops the program if the upper bound is smaller than the lower bound, so 1..<0 would crash. The lesson's numbers are between 1 and 10,000, so the range is always valid. For n = 1, 1..<1 is a valid empty range.
The divisors in the examples
Running the divisor loop shows the pieces that add up. For 28 the divisors below it are 1, 2, 4, 7 and 14, which sum to 28. For 12 they are 1, 2, 3, 4 and 6, which sum to 16, more than 12, so 12 is not perfect. For 496 they are 1, 2, 4, 8, 16, 31, 62, 124 and 248, which sum to 496.
How much work this is
The helper tries n - 1 candidates for a number n. With at most 20 numbers of at most 10,000 each, that is under 200,000 checks, which a computer finishes at once. A smarter search that stops at the square root of n exists, but it adds complexity the lesson doesn't need.
Why a helper is worth it
The question "is this number perfect?" has a clear shape: compare a number with a sum. The helper computes the sum, and perfectNumbers does the comparing. Each function is short enough to read in one glance.
The three examples give:
[6, 28]
[]
[496, 6, 6]
The helper alone returns these sums: sumOfDivisors(6) is 6, sumOfDivisors(8) is 7, sumOfDivisors(12) is 16, sumOfDivisors(1) is 0, sumOfDivisors(5) is 1 and sumOfDivisors(10) is 8.
Another way, once built-ins are allowed
Swift can express the helper in one line: (1..<n).filter { n % $0 == 0 }.reduce(0, +). It keeps the divisors and adds them up. It returns 6 for 6, 28 for 28, 16 for 12 and 0 for 1, the same answers as the loop. The loop spells out each step, so it is the better form for learning.
Edge cases
The number 1 is the one the rule treats specially: the loop over 1..<1 does nothing, the sum is 0, and 1 is not equal to 0, so it is not perfect. Prime numbers such as 5 have exactly one smaller divisor, 1, so their sum is 1, which only equals the number when the number is 1. Among the numbers up to 10,000, the perfect ones are 6, 28, 496 and 8128.
Common mistakes
- Including
nitself. With1...nthe sum for 6 would be 12, not 6, so 6 would no longer be found. Only 1 would match, wrongly. - Treating 1 as perfect. Its sum is 0, not 1, because 1 is not smaller than itself.
- Dropping duplicates. The result keeps a perfect number every time it appears.
- Putting the divisor loop in
perfectNumbers. The lesson keeps it in the helper, so the second function only compares.
