Domain 1EasyCORE

Perfect Number

The problem asks us to determine if a given integer `n` is a perfect number. A perfect number is defined as a positive integer that is equal to the sum of its positive divisors, excluding the number itself. The input is a single integer `n`, and the output should be a boolean value: `true` if `n` is a perfect number, otherwise `false`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math

507. Perfect Number

Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 36.3%


Problem Breakdown

The problem asks us to determine if a given integer n is a perfect number. A perfect number is defined as a positive integer that is equal to the sum of its positive divisors, excluding the number itself. The input is a single integer n, and the output should be a boolean value: true if n is a perfect number, otherwise false.

Inputs:

  • A single integer n where 1 <= n <= 10^8.

Outputs:

  • A boolean value (true or false).

Implicit Constraints and Edge Cases:

  • The smallest possible input is 1, which has no divisors other than itself, so it should return false.
  • Numbers like 2, 3, etc., that are not perfect numbers should return false.

Intuition

The brute-force approach would involve iterating through all integers from 1 to n-1 to check if they are divisors of n. If the sum of these divisors equals n, then n is a perfect number. However, this approach has a time complexity of O(n), which is inefficient given the constraint n <= 10^8.

A more efficient approach leverages the fact that divisors come in pairs. For example, if d is a divisor of n, then n/d is also a divisor. This insight allows us to reduce the number of iterations significantly by only checking up to the square root of n. If d is a divisor and d != n/d, both d and n/d should be added to the sum of divisors.

Approach

  1. Edge Case Handling: If n is less than or equal to 1, return false immediately since no number less than or equal to 1 can be a perfect number.
  2. Initialize Variables: Start with a variable sum_of_divisors initialized to 1 (since 1 is a divisor of every positive integer).
  3. Iterate Over Possible Divisors: Loop from i = 2 to the square root of n. For each i, check if it divides n evenly.
    • If i is a divisor, add both i and n/i to sum_of_divisors.
    • To avoid adding the square root twice when i * i == n, ensure that i != n/i.
  4. Check for Perfect Number: After the loop, compare sum_of_divisors with n. If they are equal, return true; otherwise, return false.

Complexity Analysis

  • Time Complexity: O(√n) because we only iterate up to the square root of n.
  • Space Complexity: O(1) since we use a constant amount of extra space.

Solution

def checkPerfectNumber(num: int) -> bool:
    if num <= 1:
        return False
    
    sum_of_divisors = 1
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            sum_of_divisors += i
            if i != num // i:
                sum_of_divisors += num // i
    
    return sum_of_divisors == num

Edge Cases Handled

  • Edge Case 1: num = 1 - Returns false because 1 has no divisors other than itself.
  • Edge Case 2: num = 2 - Returns false because the only divisor is 1, and 1 + 0 != 2.
  • Perfect Numbers: The function correctly identifies known perfect numbers like 6, 28, 496, and 8128 by returning true.
  • Non-perfect Numbers: Any number that does not meet the criteria for a perfect number returns false.