Start learning free

LESSON 244 OF 667 · HELPER FUNCTIONS

Perfect Numbers in C++: A Divisor-Sum Helper

Practice Read the full explanation

You get a vector of integers nums. Return the perfect numbers among them, in the same order.

A number is perfect when it equals the sum of its divisors 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.

If a perfect number appears twice, it is kept twice. If no number is perfect, the result is empty.

The work is split between two functions. The first one is a helper. It gets one number and returns the sum of its divisors smaller than itself. The second one is the function that is graded. It keeps every number that equals the sum the helper returns for it.

 

Example 1:

Input: nums = [6, 8, 28, 12]
Output: [6, 28]
Explanation: 6 = 1 + 2 + 3.
28 = 1 + 2 + 4 + 7 + 14.
For 8, the sum is 1 + 2 + 4 = 7.
For 12, the sum is 1 + 2 + 3 + 4 + 6 = 16.

Example 2:

Input: nums = [1, 5, 10]
Output: []
Explanation: The sum for 1 is 0.
The sum for 5 is 1.
The sum for 10 is 1 + 2 + 5 = 8.

Example 3:

Input: nums = [496, 6, 6]
Output: [496, 6, 6]
Explanation: 496 is perfect too.
6 appears twice, so it is kept twice.

 

Constraints:

  • nums has 1 to 20 numbers.
  • Every number is between 1 and 10,000.
STEP 1 OF 8
    Ctrl + Enter to check

    C++ · HELPER FUNCTIONS

    Perfect Numbers in C++, explained

    Problem overview

    The function perfectNumbers gets a vector 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 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, and if none is perfect 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: 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 answer is empty, since the sums are 0, 1 and 8. For {496, 6, 6} it is 496 6 6. The tests print a vector as its values separated by spaces.

    The work is split in two functions. The helper sumOfDivisors returns the sum of the smaller divisors of one number. perfectNumbers keeps every number that equals what the helper returns for it.

    Approach

    A number d divides n exactly when n % d == 0, meaning the remainder is 0. The helper tries every d from 1 up to, but not including, n, and adds up the ones that divide. Leaving out n itself is the rule: only divisors smaller than the number count.

    For n = 1 the loop runs zero times and the sum stays 0, so 1 is never perfect. The main function then needs only a comparison: sumOfDivisors(num) == num.

    Trying every number below n is slow for a huge n, but here n is at most 10,000 and there are at most 20 numbers, so it is quick.

    Two numbers worked through

    For 12, the divisors below 12 are 1, 2, 3, 4 and 6. They add up to 16, which is not 12, so 12 is left out. For 28, the divisors below 28 are 1, 2, 4, 7 and 14, which add up to 28, so 28 is perfect. The loop finds these by trying each d in turn and keeping the ones that leave no remainder.

    Notice that 12 gives a sum bigger than itself and 8 gives a sum smaller than itself. A perfect number is the exact middle case, which is why the test is == and not < or >.

    Step by step

    1. In sumOfDivisors, create total as an int starting at 0.
    2. Loop with d from 1 while d < n.
    3. If n % d == 0, add d to total.
    4. Return total.
    5. In perfectNumbers, start with an empty vector<int> named perfect.
    6. Loop over nums with an int named num. A perfect number that appears twice is visited twice, so it is kept twice.
    7. If sumOfDivisors(num) == num, add num with push_back.
    8. Return perfect after the loop.

    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;
    }

    vector<int> perfectNumbers(vector<int> &nums) {
        vector<int> perfect;
        for (int num : nums) {
            if (sumOfDivisors(num) == num) {
                perfect.push_back(num);
            }
        }
        return perfect;
    }
};

    Notes on the C++:

    • The loop variable d lives only inside the for, and total is local to the helper, so each call starts fresh at 0.
    • % gives the remainder of an integer division. All the numbers here are positive, so there is no sign to worry about.
    • Sums of divisors for numbers up to 10,000 stay far below the largest int, so there is no overflow.

    Take the third example, {496, 6, 6}. The loop visits 496 first: the helper sums its divisors below 496 and gets 496, so 496 is added to perfect. The loop then visits 6 and gets 6, so 6 is added, and the second 6 is added the same way. The result is 496 6 6.

    Complexity

    For one number n the helper makes about n turns. The main function calls it once per number, so the total is about the sum of all the numbers in nums. With 20 numbers of at most 10,000 that is at most 200,000 turns.

    Edge cases and common mistakes

    • Including n itself. With d <= n, the sum for 6 becomes 12, so no number would ever be perfect.
    • The number 1. Its sum is 0, not 1, so it is not perfect.
    • Starting the loop at 0. n % 0 is a division by zero, which is undefined behaviour in C++. The loop starts at 1.
    • Removing duplicates. The task keeps a repeated perfect number every time it appears.
    • Larger perfect numbers. 496 and 8128 pass the same test as 6 and 28.

    Testing

    • {6, 8, 28, 12} gives 6 28.
    • {1, 5, 10} gives an empty vector.
    • {496, 6, 6} gives 496 6 6.
    • {8128} gives 8128.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free