Problem overview
The method perfectNumbers gets an Array[Int] called nums and returns the perfect numbers among them, in the same order, as an ArrayBuffer[Int]. A number is perfect when it equals the sum of its divisors that are smaller than itself. For 6 those divisors are 1, 2 and 3, and 1 + 2 + 3 = 6. The number 1 has no smaller divisors, so its sum is 0 and it is not perfect. A perfect number that appears twice is kept twice, and if there are none the result is empty. There are 1 to 20 numbers, each between 1 and 10,000.
For [6, 8, 28, 12] the answer is [6, 28]. For [1, 5, 10] it is empty, and for [496, 6, 6] it is [496, 6, 6].
Approach
The work is split between two methods. The helper sumOfDivisors takes one number n and returns the sum of its divisors smaller than n. perfectNumbers calls it on every number and keeps the ones where the helper's answer equals the number. The helper tries every candidate d from 1 up to n - 1 and adds those that divide n with no remainder. With numbers up to 10,000 that is at most about ten thousand checks per number, which is fast.
Step by step
The helper
- Create
totalwithvar, starting at 0. - Loop with
for (d <- 1 until n). The range1 until ncovers 1 ton - 1, sonitself is left out, as the rule asks. Forn = 1the range is empty and the sum stays 0. - If
n % d == 0, thenddividesnevenly, so add it tototal. - After the loop, return
total.
The main method
- Create an empty
ArrayBuffer[Int]calledperfect. - Loop with
for (num <- nums). - If
sumOfDivisors(num) == num, appendnumwith+=. - Return
perfect.
The solution in Scala
class Solution {
def sumOfDivisors(n: Int): Int = {
var total = 0
for (d <- 1 until n) {
if (n % d == 0) {
total += d
}
}
return total
}
def perfectNumbers(nums: Array[Int]): ArrayBuffer[Int] = {
val perfect = ArrayBuffer[Int]()
for (num <- nums) {
if (sumOfDivisors(num) == num) {
perfect += num
}
}
return perfect
}
}
The helper has its own loop, and the main method only calls it, once per number. A perfect number that appears twice is visited twice, so it is kept twice. 1 until n excludes its upper end, while 1 to n would include it and add n itself to the sum.
Why this works
Every number from 2 up has at least one divisor smaller than itself, namely 1, so most sums are at least 1. A sum can come out smaller than the number (a number with few divisors, like 5, has the sum 1), equal to it (a perfect number) or bigger than it (a number with many divisors, like 12 or 10,000). The test sumOfDivisors(num) == num accepts only the middle case.
In the main method the helper's answer is compared with num using ==, which compares numbers by value. The helper is called once per number, so for the second example it is called three times, with 1, 5 and 10, and none of the three answers (0, 1 and 8) equals its number. That is why the result stays empty.
Testing
The helper returns these sums for 1, 5, 6, 8, 10, 12, 28 and 496 in order: 0, 1, 6, 7, 8, 16, 28 and 496. So 6, 28 and 496 equal their sums, and the others do not. The three examples return 6 28, an empty buffer and 496 6 6 (the tests print lists as values separated by spaces).
A number can be bigger than its sum, as 8 is (7), or smaller, as 12 is (16). Only an exact match counts as perfect.
Another way
A divisor of n that is smaller than n is never bigger than n / 2, so the helper can stop there:
def sumOfDivisors(n: Int): Int = {
var total = 0
for (d <- 1 to n / 2) {
if (n % d == 0) {
total += d
}
}
return total
}
It returns the same sums as the lesson's version for every number from 1 to 10,000, with about half the checks. For 1 the range 1 to 0 is empty, so the sum is still 0. The lesson's version is the simpler one to read, and for at most 20 numbers up to 10,000 either is fast.
The main loop can also be written with filter: nums.filter(n => sumOfDivisors(n) == n) keeps 6 28 on the first example, but it returns an Array, not the ArrayBuffer the method must return.
Edge cases and common mistakes
- Including
nitself. With1 to n, every sum grows by exactlyn. Then 6 and 28 no longer match, and 1 wrongly does: on[6, 8, 28, 12, 1]the result is1instead of6 28. - The number 1. Its range is empty, the sum is 0, and 1 is correctly not perfect.
- Using
/instead of%. The test is a remainder of 0, writtenn % d == 0. - Removing duplicates. The statement keeps a repeated perfect number every time it appears, so the main method must not skip numbers it has seen.
- Comparing with the wrong value. Compare the helper's answer with
num, not withtotalor a fixed value like 6.
