Problem overview
This lesson has two functions. The helper sum_of_divisors receives a whole number n and returns the sum of its divisors that are smaller than n. The function that is tested, perfect_numbers, receives a vector nums and returns the perfect numbers among them, in the same order. A number is perfect when it equals the sum of its smaller divisors: 6 is perfect because 1 + 2 + 3 = 6. The number 1 is not perfect, since it has no smaller divisors and its sum is 0. A perfect number that appears twice is kept twice, and if there are none 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, so neither equals itself. For [1, 5, 10] the result is [], and for [496, 6, 6] the result is [496, 6, 6]. The vector has 1 to 20 numbers, each between 1 and 10,000.
Approach
Split the work. The helper tries every candidate d from 1 up to n - 1 and adds it to a total when n % d == 0, that is, when dividing by d leaves no remainder. With the limits of 10,000 per number and 20 numbers, trying every candidate is fast enough: at most about 200,000 divisions. Then perfect_numbers loops over the vector and keeps each number that equals the helper's answer for it.
Step by step
- In
sum_of_divisors, startlet mut total = 0;. Forn = 1the loop never runs, so the sum stays 0. - Loop
dover1..n. In Rust a range excludes its end, so this is 1 up ton - 1, andnitself is left out as the task requires. - If
n % d == 0, adddtototal. - Return
total. - In
perfect_numbers, create an empty mutableVecnamedperfect. Rust infers its element type from what is pushed. - Loop over
&nums. WhenSelf::sum_of_divisors(*num)equals*num, push*num. - Return
perfect.
The solution in Rust
impl Solution {
fn sum_of_divisors(n: i32) -> i32 {
let mut total = 0;
for d in 1..n {
if n % d == 0 {
total += d;
}
}
return total;
}
fn perfect_numbers(nums: Vec<i32>) -> Vec<i32> {
let mut perfect = Vec::new();
for num in &nums {
if Self::sum_of_divisors(*num) == *num {
perfect.push(*num);
}
}
return perfect;
}
}
Rust details
- Ranges.
1..nstops beforen;1..=nwould include it. With1..=nthe helper would addnitself, so the sum for 6 would be 12 instead of 6, and no number could ever equal its sum. - The variable
d. Infor d in 1..neachdis a plaini32, not a reference, because a range produces numbers by value. In the second function,numis a reference because the loop goes over&nums, hence*num. - Calling the helper. Both functions live in an
implblock, so one is called asSelf::sum_of_divisors(...).
Why the sums work out
Take 12. The candidates 1 to 11 are tried in turn, and only 1, 2, 3, 4 and 6 leave no remainder, so sum_of_divisors(12) is 16. Since 16 is not 12, the number 12 is skipped. For 28 the divisors are 1, 2, 4, 7 and 14, and they add up to exactly 28, so it is kept. A number whose sum is smaller than itself (like 8, with 7) is called deficient, and one whose sum is bigger (like 12) is abundant. A perfect number is the exact middle.
The loop in the helper is written so that no special case is needed. For n = 1 the range 1..1 is empty. For a prime such as 5 the only divisor below it is 1, so the sum is 1.
Trying it
perfect_numbers([6, 8, 28, 12]) -> [6, 28]
perfect_numbers([1, 5, 10]) -> []
perfect_numbers([496, 6, 6]) -> [496, 6, 6]
perfect_numbers([8128, 10000]) -> [8128]
sum_of_divisors(1), (8), (12), (28) -> 0, 7, 16, 28
The smallest perfect numbers are 6, 28, 496 and 8128. The last is the biggest one that fits in the lesson's limit of 10,000.
Could the helper be faster?
Yes. Divisors come in pairs: if d divides n, so does n / d. So you can stop searching at the square root of n and add both numbers of each pair, taking care not to count a square root twice and not to include n itself. With numbers up to 10,000 and at most 20 of them, the plain loop is already instant, so the lesson keeps the simple version. It is also the version that is easiest to get right.
Common mistakes
- Including
nin the sum. Every number is a divisor of itself, but the task wants only the smaller ones. Using1..=nbreaks it. - Starting the range at 0.
n % 0divides by zero and stops the program with a panic. - Treating 1 as perfect. Its sum is 0, not 1. The loop over
1..1is empty, so the code gets this right with no special case. - Removing repeats. The task keeps a perfect number every time it appears, so there is no set and no de-duplication.
