Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Perfect Number Check

Try it yourself
EasyProblem

Description

Given a positive integer n, return true if it is a perfect number and false if it isn't.

A perfect number equals the sum of its divisors smaller than itself. 6 is perfect: its smaller divisors are 1, 2 and 3, and 1 + 2 + 3 = 6.

Examples

Example 1

Input: n = 28

Output: true

Explanation: Its smaller divisors are 1, 2, 4, 7 and 14, and 1 + 2 + 4 + 7 + 14 = 28.

Example 2

Input: n = 12

Output: false

Explanation: 1 + 2 + 3 + 4 + 6 = 16, more than 12.

Example 3

Input: n = 1

Output: false

Explanation: 1 has no divisor smaller than itself, so the sum is 0.

Example 4

Input: n = 6

Output: true

Explanation: 1 + 2 + 3 = 6.

Constraints

  • 1 ≤ n ≤ 10^8

Editorial

Brute Force - Try Every Candidate

Intuition

A divisor of n smaller than n is a number from 1 to n - 1 that leaves no remainder. Try each one, add up those that divide n, and compare the sum with n.

Step-by-Step Explanation

Let's trace Example 1, n = 28:

  1. Try each d from 1 to 27; the ones that divide 28 are 1, 2, 4, 7, 14.
  2. Their sum is 1 + 2 + 4 + 7 + 14 = 28.
  3. 28 equals 28: return true.

Every Candidate — Every number below 28 tried in turn; the divisors light up.

Algorithm

  1. Start a total at 0.
  2. For each d from 1 to n - 1: if n % d == 0, add d.
  3. Return whether the total equals n.

Code

class Solution {
public:
    bool isPerfectNumber(int n) {
        long long total = 0;
        for (int d = 1; d < n; d++) {       // every candidate below n
            if (n % d == 0) total += d;
        }
        return total == n;
    }
};

class Solution:
    def isPerfectNumber(self, n: int) -> bool:
        total = 0
        for d in range(1, n):               # every candidate below n
            if n % d == 0:
                total += d
        return total == n

class Solution {
    public boolean isPerfectNumber(int n) {
        long total = 0;
        for (int d = 1; d < n; d++) {       // every candidate below n
            if (n % d == 0) total += d;
        }
        return total == n;
    }
}

var isPerfectNumber = function(n) {
    let total = 0;
    for (let d = 1; d < n; d++) {           // every candidate below n
        if (n % d === 0) total += d;
    }
    return total === n;
};

Complexity Analysis

Time Complexity: O(n)

It tries every number below n.

Space Complexity: O(1)

One running total.

Why This Approach Is Not Efficient

n goes up to 10^8, and so does the number of candidates. On our judge it took 99 ms for n = 1,000,000 and 722 ms for n = 10,000,000 in Python: ten times the candidates, 7 times the time. The tests include n near 10^8, and it ran out of time on those in Python.

Most candidates are wasted. Divisors come in pairs: when d divides n, so does n / d, and one of the two is at most √n. So trying d up to √n finds every pair.

Optimal Approach - Divisor Pairs up to √n

Intuition

For each d from 2 while d × d ≤ n, if d divides n, add both d and its partner n / d. Start the total at 1, since 1 divides every n above 1, and leave n itself out, since only the divisors smaller than n count.

Two cases need care. When d × d is exactly n, d is its own partner, so add it once. And 1 has no divisor smaller than itself, so it's never perfect.

Step-by-Step Explanation

Let's trace Example 1 again, n = 28:

  1. 1 divides every n above 1: the total starts at 1. √28 is about 5.29, so d goes from 2 to 5.
  2. d = 2 divides 28; so does 28 / 2 = 14. Add both: the total is 17.
  3. d = 3 doesn't divide 28.
  4. d = 4 divides 28; so does 28 / 4 = 7. Add both: the total is 28.
  5. d = 5 doesn't divide 28.
  6. 6 × 6 = 36 is past 28: stop. The total, 28, equals 28: return true.

Divisor Pairs up to √n — Only d from 2 to 5 are tried; each divisor found brings its partner.

Algorithm

  1. If n is 1, return false.
  2. Start the total at 1.
  3. For each d from 2 while d * d <= n: if n % d == 0, add d, and add n / d too unless it equals d.
  4. Return whether the total equals n.

Code

On our judge it took 30 ms for n = 100,000,000 in Python: 10,000 candidates instead of 100,000,000. In Java and C++ the loop counts with a long, so d * d can't overflow.

class Solution {
public:
    bool isPerfectNumber(int n) {
        if (n == 1) return false;               // 1 has no divisor smaller than itself
        long long total = 1;                    // 1 divides every n > 1
        for (long long d = 2; d * d <= n; d++) {
            if (n % d == 0) {
                total += d;
                if (d != n / d) total += n / d; // its partner, unless d is the square root
            }
        }
        return total == n;
    }
};

class Solution:
    def isPerfectNumber(self, n: int) -> bool:
        if n == 1:
            return False                    # 1 has no divisor smaller than itself
        total = 1                           # 1 divides every n > 1
        d = 2
        while d * d <= n:
            if n % d == 0:
                total += d
                if d != n // d:             # its partner, unless d is the square root
                    total += n // d
            d += 1
        return total == n

class Solution {
    public boolean isPerfectNumber(int n) {
        if (n == 1) return false;               // 1 has no divisor smaller than itself
        long total = 1;                         // 1 divides every n > 1
        for (long d = 2; d * d <= n; d++) {
            if (n % d == 0) {
                total += d;
                if (d != n / d) total += n / d; // its partner, unless d is the square root
            }
        }
        return total == n;
    }
}

var isPerfectNumber = function(n) {
    if (n === 1) return false;              // 1 has no divisor smaller than itself
    let total = 1;                          // 1 divides every n > 1
    for (let d = 2; d * d <= n; d++) {
        if (n % d === 0) {
            total += d;
            if (d !== n / d) total += n / d;    // its partner, unless d is the square root
        }
    }
    return total === n;
};

Complexity Analysis

Time Complexity: O(√n)

d stops at √n: 10,000 steps for n = 10^8.

Space Complexity: O(1)

One running total.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Counting 1 as perfect. total = 1

On n = 1 it returns true; the answer is false. Starting the total at 1 is right for every n above 1, since 1 divides it. But 1 itself has no divisor smaller than itself, so its sum is 0 and it isn't perfect.

Counting n among its divisors. d = 1

On n = 28 it returns false; the answer is true. Starting the pairs at d = 1 adds 1 and its partner n / 1, which is n itself. The sum then always passes n, so nothing comes out perfect. Only the divisors smaller than n count.

Stopping just before the square root. range(2, int(n ** 0.5))

On n = 6 it returns false; the answer is true. range(2, int(n ** 0.5)) leaves out its end, int(n ** 0.5), so a divisor sitting exactly there is never tried: for 6 the loop is empty and the pair 2 and 3 is missed. The last d to try is the largest with d × d ≤ n.

Where This Pattern Is Taught

This problem practises a loop over divisors that stops at √n, and the remainder test for divisibility. It's taught in Python for DSA, Java for DSA, C++ for DSA and JavaScript for DSA.