LeetCode 507: Perfect Number

Problem Restatement

A positive integer is called a perfect number if the sum of its positive divisors excluding itself equals the number.

We are given an integer num.

We need to determine whether num is a perfect number.

The official problem defines a perfect number as a positive integer equal to the sum of all its positive divisors excluding itself. (leetcode.com)

Input and Output

Function shape:

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        ...

Examples

Example 1:

num = 28

The positive divisors excluding 28 are:

1, 2, 4, 7, 14

Their sum is:

1 + 2 + 4 + 7 + 14 = 28

So the answer is:

True

Example 2:

num = 7

The divisors excluding 7 are:

1

Their sum is:

1

Since:

1 != 7

the answer is:

False

First Thought: Check Every Divisor

A direct approach is to try every number from 1 to num - 1.

If a number divides num, add it to the sum.

total = 0

for d in range(1, num):
    if num % d == 0:
        total += d

Finally:

return total == num

This works, but it is inefficient for large numbers.

Problem With Brute Force

The brute force solution checks almost every smaller number.

That costs:

O(n)

However, divisors appear in pairs.

For example, if:

28 % 2 == 0

then:

28 / 2 = 14

So discovering divisor 2 also gives divisor 14.

This means we only need to search up to:

√num

Key Insight

If:

d divides num

then:

num // d

is also a divisor.

Divisors come in symmetric pairs around the square root.

For example:

for:

28

So we can find all divisors by checking only numbers from:

2 to √num

The divisor 1 is always included for numbers greater than 1.

Algorithm

Handle small values first.

A perfect number must be positive and greater than 1.

So:

if num <= 1:
    return False

Initialize:

total = 1

because 1 is always a divisor.

Then iterate:

for d in range(2, int(num ** 0.5) + 1):

If d divides num:

1. Add d
2. Add its paired divisor num // d

Be careful with perfect squares.

If:

d * d == num

then both divisors are the same, so add it only once.

Finally:

return total == num

Correctness

The algorithm checks every integer d from 2 to √num.

Whenever d divides num, both:

d

and:

num // d

are positive divisors of num.

Every divisor greater than √num is paired with a divisor smaller than √num, so no divisor is missed.

The divisor 1 is included separately at initialization.

For perfect squares, the square root divisor appears only once, and the algorithm correctly avoids double-counting it.

Therefore total equals the sum of all positive divisors excluding num itself.

The algorithm returns True exactly when this sum equals num, which matches the definition of a perfect number.

Complexity

Implementation

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num <= 1:
            return False

        total = 1

        limit = int(num ** 0.5)

        for d in range(2, limit + 1):
            if num % d == 0:
                total += d

                pair = num // d

                if pair != d:
                    total += pair

        return total == num

Code Explanation

Numbers less than or equal to 1 cannot be perfect:

if num <= 1:
    return False

The divisor 1 is always included:

total = 1

We only check divisors up to the square root:

limit = int(num ** 0.5)

If d divides num:

if num % d == 0:

then d is a divisor:

total += d

and its paired divisor is:

pair = num // d

For non-square cases, add the paired divisor too:

if pair != d:
    total += pair

Finally, compare the divisor sum with the original number:

return total == num

Testing

def test_check_perfect_number():
    s = Solution()

    assert s.checkPerfectNumber(28) is True
    assert s.checkPerfectNumber(6) is True
    assert s.checkPerfectNumber(496) is True

    assert s.checkPerfectNumber(7) is False
    assert s.checkPerfectNumber(1) is False
    assert s.checkPerfectNumber(12) is False

    print("all tests passed")

Test meaning: