LeetCode 507 - Perfect Number

This problem asks us to determine whether a given positive integer num is a perfect number. A perfect number is defined as a number whose sum of positive divisors, excluding the number itself, equals the number.

leetcodeeasymath

LeetCode Problem 507

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

This problem asks us to determine whether a given positive integer num is a perfect number.

A perfect number is defined as a number whose sum of positive divisors, excluding the number itself, equals the number. In other words, we must find all integers that divide num evenly, excluding num, sum them up, and check whether that sum equals the original number.

For example, consider 28:

  • 1 divides 28
  • 2 divides 28
  • 4 divides 28
  • 7 divides 28
  • 14 divides 28

The sum of these divisors is:

1 + 2 + 4 + 7 + 14 = 28

Since the sum equals the number itself, 28 is a perfect number.

The input consists of a single integer num, and the output should be:

  • true if num is a perfect number
  • false otherwise

The constraints tell us:

  • 1 <= num <= 10^8

This upper bound is important. A naive solution that checks every number from 1 to num - 1 would require up to 10^8 operations in the worst case, which is inefficient. We need a better approach.

An important mathematical observation is that divisors appear in pairs. For example, for 28:

  • 2 × 14 = 28
  • 4 × 7 = 28

If we find one divisor, we automatically know another. This allows us to check only up to √num, which significantly improves performance.

Several edge cases deserve attention:

  • num = 1 is not a perfect number because it has no positive divisors excluding itself, so the sum is 0, not 1.
  • Perfect squares require careful handling to avoid counting the square root twice.
  • Small non-perfect numbers such as 2 or 7 should correctly return false.

Approaches

Brute Force Approach

The most straightforward approach is to iterate through every integer from 1 to num - 1, check whether it divides num, and add it to a running sum if it does.

This works because it explicitly computes the sum of all proper divisors. If the final sum equals num, then the number is perfect.

However, this method is inefficient. In the worst case, we check nearly 10^8 numbers, which is unnecessarily expensive given the problem constraints.

Key Insight for an Optimal Solution

The key mathematical insight is that divisors come in complementary pairs.

If d divides num, then num / d must also divide num.

For example, with 28:

  • Finding divisor 2 automatically gives divisor 14
  • Finding divisor 4 automatically gives divisor 7

This means we only need to search up to √num.

We initialize the divisor sum with 1, since 1 is always a proper divisor for numbers greater than 1. Then, for every divisor d between 2 and √num:

  • Add d
  • Add num // d

If d * d == num, we only add the divisor once because both values are identical.

This reduces the time complexity from O(n) to O(√n).

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Checks every number from 1 to num - 1
Optimal O(√n) O(1) Uses divisor pairing to reduce work

Algorithm Walkthrough

  1. Handle the special case for 1

Since 1 has no proper divisors, it cannot be a perfect number. Return false immediately. 2. Initialize the divisor sum

Start with divisor_sum = 1 because 1 is always a valid divisor for any number greater than 1. 3. Iterate from 2 to √num

We only need to check divisors up to the square root because every divisor larger than √num has a matching smaller divisor. 4. Check divisibility

For each candidate divisor d, check whether num % d == 0. If true, d is a divisor. 5. Add both divisors in the pair

Add d to the sum. Then compute the paired divisor:

paired_divisor = num // d

If d and paired_divisor are different, add both. 6. Avoid double-counting perfect squares

When d * d == num, the divisor pair is actually the same number. Add it only once. 7. Compare the sum to the original number

After processing all divisors, return whether divisor_sum == num.

Why it works

The algorithm works because every divisor of a number appears in a unique pair around √num. By iterating only up to the square root and adding both divisors together, we account for every proper divisor exactly once. The special handling for perfect squares ensures no divisor is counted twice. Therefore, the computed sum is exactly the sum of all proper divisors, which guarantees correctness.

Python Solution

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

        divisor_sum = 1
        divisor = 2

        while divisor * divisor <= num:
            if num % divisor == 0:
                divisor_sum += divisor

                paired_divisor = num // divisor
                if paired_divisor != divisor:
                    divisor_sum += paired_divisor

            divisor += 1

        return divisor_sum == num

The implementation begins by handling the special case where num == 1, since 1 cannot be perfect.

We initialize divisor_sum to 1 because every integer greater than 1 has 1 as a proper divisor. Then we iterate through possible divisors starting from 2.

The loop condition:

divisor * divisor <= num

ensures we only search up to √num.

Whenever we find a divisor, we add it to the running total and compute its paired divisor using integer division. If the paired divisor differs from the current divisor, we add it as well. This prevents double-counting in cases where num is a perfect square.

Finally, the function compares the accumulated divisor sum against num and returns the result.

Go Solution

func checkPerfectNumber(num int) bool {
    if num == 1 {
        return false
    }

    divisorSum := 1

    for divisor := 2; divisor*divisor <= num; divisor++ {
        if num%divisor == 0 {
            divisorSum += divisor

            pairedDivisor := num / divisor
            if pairedDivisor != divisor {
                divisorSum += pairedDivisor
            }
        }
    }

    return divisorSum == num
}

The Go implementation follows the exact same logic as the Python solution.

Since Go uses explicit variable declarations, we define divisorSum as an integer and use a standard for loop for iteration. Integer division is handled naturally using / because both operands are integers.

Integer overflow is not a concern here because num ≤ 10^8, and the divisor sum remains well within Go's int range.

Worked Examples

Example 1: num = 28

We initialize:

divisor_sum = 1

We check divisors from 2 to √28 ≈ 5.

Divisor Divides 28? Paired Divisor Updated Sum
2 Yes 14 1 + 2 + 14 = 17
3 No - 17
4 Yes 7 17 + 4 + 7 = 28
5 No - 28

Final check:

divisor_sum = 28

Since 28 == 28, return true.

Example 2: num = 7

We initialize:

divisor_sum = 1

We check divisors from 2 to √7 ≈ 2.

Divisor Divides 7? Paired Divisor Updated Sum
2 No - 1

Final check:

divisor_sum = 1

Since 1 != 7, return false.

Complexity Analysis

Measure Complexity Explanation
Time O(√n) We only check divisors up to the square root of num
Space O(1) Only a few variables are used

The efficiency comes from the divisor pairing property. Instead of examining every integer below num, we only examine values up to √num, which dramatically reduces the number of iterations. The algorithm uses constant additional memory regardless of input size.

Test Cases

solution = Solution()

assert solution.checkPerfectNumber(28) is True   # Provided example, perfect number
assert solution.checkPerfectNumber(7) is False   # Provided example, prime number

assert solution.checkPerfectNumber(1) is False   # Minimum boundary value
assert solution.checkPerfectNumber(2) is False   # Smallest prime
assert solution.checkPerfectNumber(6) is True    # Small perfect number
assert solution.checkPerfectNumber(496) is True  # Larger perfect number
assert solution.checkPerfectNumber(8128) is True # Known perfect number

assert solution.checkPerfectNumber(16) is False  # Perfect square, avoid double-counting sqrt
assert solution.checkPerfectNumber(25) is False  # Another perfect square
assert solution.checkPerfectNumber(99999999) is False  # Large non-perfect number
assert solution.checkPerfectNumber(100000000) is False # Maximum constraint value
Test Why
28 Validates provided perfect number example
7 Validates provided non-perfect example
1 Tests smallest input and special case
2 Tests small prime number
6 Validates smallest perfect number
496 Tests known larger perfect number
8128 Tests another known perfect number
16 Ensures perfect square divisors are not double-counted
25 Additional perfect square validation
99999999 Stress test with a large non-perfect number
100000000 Tests upper constraint boundary

Edge Cases

Input 1

The number 1 is a common source of bugs because many implementations initialize the divisor sum with 1. If we are not careful, the algorithm might incorrectly classify 1 as perfect.

Our implementation handles this explicitly by immediately returning false when num == 1.

Perfect Squares

Numbers such as 16 or 25 require careful treatment because the square root divisor appears only once.

For example:

16 = 4 × 4

If we blindly add both divisors in every pair, we would count 4 twice. The implementation prevents this with:

if paired_divisor != divisor:

This guarantees correctness.

Prime Numbers

Prime numbers such as 7 or 13 only have one proper divisor, 1.

A naive implementation may accidentally assume that every divisor search finds multiple factors. Our solution naturally handles primes because no divisors are found between 2 and √num, leaving the sum at 1, which correctly returns false.