Perfect Number

Difficulty: Easy | Acceptance: 48.80% | Paid: No Topics: Math

A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. A divisor of an integer x is an integer that can divide x evenly.

Given an integer num, return true if num is a perfect number, otherwise return false.

• Examples
• Constraints
• Brute Force Iteration
• Square Root Optimization
• Euclid-Euler Theorem

Examples

Example 1

Input:

num = 28

Output:

true

Explanation: 28 = 1 + 2 + 4 + 7 + 14 1, 2, 4, 7, and 14 are all divisors of 28.

Example 2

Input:

num = 7

Output:

false

Constraints

1 <= num <= 10^8

Brute Force Iteration

Intuition The most straightforward approach is to iterate through all numbers from 1 to num - 1. For each number, check if it divides num evenly. If it does, add it to a running sum. Finally, compare the sum to num.

Steps

• Initialize a sum variable to 0.
• Loop from 1 to num - 1.
• If num is divisible by the current iterator, add the iterator to the sum.
• After the loop, return true if sum equals num, otherwise false.

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num <= 1:
            return False
        total_sum = 0
        for i in range(1, num):
            if num % i == 0:
                total_sum += i
        return total_sum == num

Complexity

• Time: O(N) - We iterate up to N times.
• Space: O(1) - We only use a variable for the sum.
• Notes: This approach is inefficient for large numbers (e.g., close to 10⁸) and may result in a Time Limit Exceeded error on LeetCode.

Square Root Optimization

Intuition Divisors come in pairs. If i divides num, then num / i also divides num. For example, for 28, if we find 2, we also find 14. We only need to iterate up to the square root of num to find all divisor pairs.

Steps

• Handle edge case: if num <= 1, return false.
• Initialize sum to 1 (since 1 is always a divisor for num > 1).
• Loop from 2 up to the square root of num.
• If i divides num:
  • Add i to the sum.
  • If i is not equal to num / i (to avoid adding the square root twice), add num / i to the sum.
• Return true if sum equals num, otherwise false.

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num <= 1:
            return False
        total_sum = 1
        i = 2
        while i * i <= num:
            if num % i == 0:
                total_sum += i
                if i != num // i:
                    total_sum += num // i
            i += 1
        return total_sum == num

Complexity

• Time: O(√N) - We iterate only up to the square root of N.
• Space: O(1) - Constant space usage.
• Notes: This is the standard optimal approach for general divisor sum problems.

Euclid-Euler Theorem

Intuition According to the Euclid-Euler theorem, every even perfect number can be represented as 2^(p-1) * (2^p - 1), where (2^p - 1) is a prime number (specifically a Mersenne prime). Given the constraint 1 <= num <= 10⁸, there are only a few perfect numbers that exist. We can simply check if the input matches one of these known values.

Steps

• Identify the list of perfect numbers within the constraint range: 6, 28, 496, 8128, 33550336.
• Check if the input num exists in this set.
• Return true if it does, false otherwise.

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        # Known perfect numbers within the 10^8 limit
        return num in {6, 28, 496, 8128, 33550336}

Complexity

• Time: O(1) - Set lookup or simple comparison is constant time.
• Space: O(1) - The set of known numbers is fixed and very small.
• Notes: This is the fastest solution for this specific problem due to the limited input range, but it relies on mathematical pre-knowledge rather than algorithmic calculation.