Problem overview
The function perfectNumbers gets 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. The number 6 is perfect, because 1 + 2 + 3 = 6. The number 1 is not: it has no smaller divisors, so its sum is 0. A perfect number that appears twice is kept twice, and if no number is perfect the result is empty. The array has 1 to 20 numbers, each from 1 to 10,000.
The work is split in two. The helper sumOfDivisors gets one number and returns the sum of its divisors smaller than itself. perfectNumbers is the function the tests call, and it keeps every number that equals the sum the helper returns for it.
For [6, 8, 28, 12] the helper returns 6, 7, 28 and 16, so the answer is [6, 28]. For [1, 5, 10] it returns 0, 1 and 8, so nothing is perfect. For [496, 6, 6] every number is perfect, so all three are kept.
Approach
To find the divisors of n that are smaller than n, try every candidate d from 1 up to n - 1. A number d divides n exactly when the remainder n % d is 0. Add each such d to a running total. With numbers up to 10,000 and at most 20 of them, trying every candidate is fast enough, so there is no need for anything cleverer.
In perfectNumbers the rule is then a one-line comparison: keep num when sumOfDivisors(num) == num.
Step by step
- In
sumOfDivisors, createvar total = 0. - Loop
dover1 until n, which means 1 ton - 1. The numbernitself is left out, because only smaller divisors count. Forn = 1the range is empty, so the sum stays 0. - Inside, if
n % d == 0, adddtototal. - Return
total. - In
perfectNumbers, create an emptymutableListOf<Int>()namedperfect, in aval. - Loop over
nums. IfsumOfDivisors(num) == num, addnumto the list. - Return
perfectafter the loop.
The solution in Kotlin
class Solution {
fun sumOfDivisors(n: Int): Int {
var total = 0
for (d in 1 until n) {
if (n % d == 0) {
total += d
}
}
return total
}
fun perfectNumbers(nums: IntArray): List<Int> {
val perfect = mutableListOf<Int>()
for (num in nums) {
if (sumOfDivisors(num) == num) {
perfect.add(num)
}
}
return perfect
}
}
Here 1 until n is a range that stops before n. Writing 1..n instead would include n itself, because n divides itself. The helper would then return 1, 12 and 56 for 1, 6 and 28, so no number above 1 could ever equal its sum, and 1 would wrongly count as perfect.
Running the helper on 6, 8, 28, 12, 1, 5, 10 gives 6, 7, 28, 16, 0, 1, 8. The tests print lists as values separated by spaces, so the examples print:
6 28
496 6 6
The second example in the lesson has no perfect number, so its result is an empty list and nothing is printed for it.
More inputs to try
The next perfect number after 496 is 8128, which is inside the allowed range: sumOfDivisors(8128) returns 8128. A number like 9999 is not perfect, since its divisor sum is 5913. The largest allowed input, 10,000, has a divisor sum of 14211, which is bigger than the number itself. That is fine: a number is only perfect when the two are equal, so bigger or smaller sums both mean no.
Reading the helper on a number that is not perfect
For 12, the candidates 1 to 11 are tried. The ones with remainder 0 are 1, 2, 3, 4 and 6, and they add up to 16. Since 16 is not 12, the number is not kept. For 8 the divisors are 1, 2 and 4, which add up to 7, again not 8. Only when the sum lands exactly on the number, as 1 + 2 + 3 does for 6, does the comparison succeed.
Complexity
The helper tries n - 1 candidates, so a number near 10,000 takes about 10,000 steps. With at most 20 numbers, that is about 200,000 steps in total, which is instant. A faster helper is possible, because divisors come in pairs d and n / d, so it is enough to try candidates up to the square root of n. With these limits it is not needed. The extra space is the result list.
Common mistakes
- Including
nin the sum. Use1 until n, not1..n. - Special-casing 1. It needs no special case: the loop for
n = 1does not run, the sum is 0, and 0 is not equal to 1. - Dropping a repeated perfect number. Each element of
numsis tested in turn, so6appearing twice stays twice. - Mixing up which number the sum is for. Compare
sumOfDivisors(num)withnum, not with another element. - Returning the sums. The task asks for the numbers, not their divisor sums.
