Problem overview
You get an int[] named nums. PerfectNumbers returns the perfect numbers among them, in the same order, as a List<int>. A number is perfect when it equals the sum of its divisors 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 none is perfect the result is empty. 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 helper SumOfDivisors takes one number n and returns the sum of the divisors of n that are smaller than n. PerfectNumbers keeps every number that equals the helper's answer for it.
To build the helper, try every candidate d from 1 up to n - 1. A candidate is a divisor when n % d == 0, meaning the remainder of the division is 0. Add the divisors up. The loop stops before n itself, because n is not smaller than itself.
Step by step
- In
SumOfDivisors, createint total = 0. Forn = 1the loop never runs, so the sum stays 0. - Loop with
for (int d = 1; d < n; d++). Using<leavesnout. - If
n % d == 0, adddtototal. - Return
total. - In
PerfectNumbers, create an emptyList<int>namedperfect. - Loop over
numswithforeach. A perfect number that appears twice is visited twice, so it is kept twice. - If
SumOfDivisors(num) == num, addnumtoperfect. - Return
perfect. It stays empty if nothing qualified.
The solution in C#
class Solution {
public int SumOfDivisors(int n) {
int total = 0;
for (int d = 1; d < n; d++) {
if (n % d == 0) {
total += d;
}
}
return total;
}
public List<int> PerfectNumbers(int[] nums) {
List<int> perfect = new List<int>();
foreach (int num in nums) {
if (SumOfDivisors(num) == num) {
perfect.Add(num);
}
}
return perfect;
}
}
The details worth knowing:
- The
%operator gives the remainder of an integer division, son % d == 0reads "ddividesnevenly". - The helper is called once per number in the array. Its loop runs up to 10,000 times for the largest allowed number, and the array has at most 20 numbers, so the total work is small.
Looking inside the helper
For 28 the loop finds these divisors below 28, and their sum is 28 itself:
1 + 2 + 4 + 7 + 14 = 28
That is why 28 is perfect. For 12 the divisors below it are 1, 2, 3, 4 and 6, which add up to 16: more than 12. A number like that is called abundant. For 8 the sum is 7, which is less than 8, so 8 is not perfect either. Only an exact match counts.
A faster helper
No divisor of n other than n itself is larger than n / 2. So the loop can stop at n / 2:
int SumOfDivisors2(int n) {
int total = 0;
for (int d = 1; d <= n / 2; d++) {
if (n % d == 0) {
total += d;
}
}
return total;
}
This version returns the same sums for every number from 1 to 10,000, and it does half the work. The lesson's version, which goes up to n - 1, is already fast for these limits and is the simpler one to read.
The perfect numbers up to 10,000
Because the numbers are limited to 10,000, only four of them can ever appear in the result: 6, 28, 496 and 8128. Running the lesson's test over every number from 1 to 10,000 finds exactly these four.
Testing
The helper's answers for 8, 12, 1, 5, 10 and 6 are:
7 16 0 1 8 6
Only 6 equals its own sum. On the statement's three examples, PerfectNumbers returns:
[6, 28]
[]
[496, 6, 6]
Edge cases and common mistakes
- Including
nas a divisor. Withd <= nthe helper returns 12 for 6, which is double the number, and no number would ever be perfect. - The number 1. Its sum is 0, not 1, so it is not perfect. The loop
d < 1never runs, which gives the right answer with no special case. - Dropping repeats. The lesson keeps a perfect number every time it appears, so don't use a set here.
- Starting
dat 0.n % 0throws aDivideByZeroExceptionfor integers. Start at 1.
What the tests rely on
The method returns numbers in their original order and never sorts or removes anything, so the result is a filtered copy of the input. Since each check is independent of the others, a longer list simply means more calls to the helper, with no change to the logic.
Checking your own version
Test the helper alone on a few numbers whose answers you can work out: a prime has only 1 as a smaller divisor, so its sum is 1; the number 1 has sum 0; and 6 has sum 6. Then run the full method on a list with a repeated perfect number and on a list with none.
If your result has the right numbers but one is missing, check that the loop bound lets every smaller divisor through, and that you compare the helper's answer with num, not with another call result.
