Problem overview
The method 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 example, 6 is perfect, because 1 + 2 + 3 = 6. 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. If none is perfect, the result is empty.
For [6, 8, 28, 12] the result 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 result is []: the sums are 0, 1 and 8. For [496, 6, 6] every number is perfect, so the result is [496, 6, 6]. There are 1 to 20 numbers, each between 1 and 10,000.
Approach: a helper for one number
The work is split in two. The helper sumOfDivisors takes one number n and returns the sum of its divisors smaller than n. perfectNumbers loops over the array and keeps each number that equals the helper's answer for it.
To find the divisors of n, try every d from 1 up to, but not including, n. A number d divides n evenly when n % d == 0, that is, when the remainder is 0. Each such d is added to a running total. With numbers up to 10,000 and at most 20 of them, trying every d is fast enough.
Step by step
- In
sumOfDivisors, create anintnamedtotal, starting at 0. - Write a
forloop withdstarting at 1 and running whiled < n. The numbernitself is left out. - Inside the loop, if
n % d == 0, adddtototal. - After the loop, return
total. - In
perfectNumbers, create an emptyList<Integer>namedperfect. - Loop over
numswith anintnamednum. - If
sumOfDivisors(num)equalsnum, addnumtoperfect. - After the loop, return
perfect.
The solution in Java
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<Integer> perfectNumbers(int[] nums) {
List<Integer> perfect = new ArrayList<>();
for (int num : nums) {
if (sumOfDivisors(num) == num) {
perfect.add(num);
}
}
return perfect;
}
}Some Java details:
- The loop uses
d < n, notd <= n. With<=the number would count itself as a divisor and the sum would always be too large byn. - For
n = 1the loop never runs, so the helper returns 0 and 1 is correctly rejected. - Both sides of
sumOfDivisors(num) == numareint, so==compares values. It would be a trap only withIntegerobjects. - The loop variable
numis anint, andperfect.add(num)boxes it into anIntegerautomatically.
The helper gives these sums: 6 gives 6, 8 gives 7, 28 gives 28, 12 gives 16, 1 gives 0, 5 gives 1, 10 gives 8 and 496 gives 496. Only 6, 28 and 496 equal their own sums.
Edge cases and common mistakes
- Counting the number itself. A loop that includes
nmakes every number's sum at leastn, and the check== numthen fails for 6 (the sum would be 12). - Starting
dat 0.n % 0throws anArithmeticExceptionfor ints. Start at 1. - The number 1. Its sum is 0, so it is not perfect.
- Returning inside the loop. The
return perfectgoes after the loop. - Repeated numbers. Nothing removes duplicates, so 6 appears twice in the result for
[496, 6, 6].
Why trying every divisor is fine here
For each number the helper does up to 9,999 checks, and there are at most 20 numbers, so the whole method does fewer than 200,000 remainder checks. That is instant. A faster helper could stop at the square root of n and add both divisors of each pair, but it needs special care for perfect squares, and this input size doesn't call for it.
Walking through the first example
For [6, 8, 28, 12], the loop asks the helper about each number in turn. For 6, the divisors below 6 are 1, 2 and 3, which sum to 6, so 6 is added to perfect. For 8, the divisors are 1, 2 and 4. They sum to 7, which is not 8, so 8 is skipped. For 28, the sum is 28, so it is added. For 12 the sum is 16, so it is skipped. The loop ends with [6, 28], in the order of the input.
Keeping the jobs apart
The helper knows how to sum divisors and nothing about perfect numbers. The main method knows the rule for a perfect number and nothing about divisors. If an answer is wrong, call sumOfDivisors alone on a number like 6 or 12 to see which half has the bug. The sum for 12 should be 16, which is more than 12, so 12 must not be in the result.
Testing
Running the solution on the three examples gives:
[6, 28]
[]
[496, 6, 6]