Leetcode – Perfect Number Solution in Python

Introduction

Perfect numbers are a classical concept in number theory, and understanding them can be both intriguing and insightful. On Leetcode, the Perfect Number problem challenges you to apply the foundational concept of perfect numbers in a programming context. In this extensive article, we will dissect the Perfect Number problem, comprehend the mathematics behind it, and explore various approaches to solving it using Python.

The Perfect Number problem on Leetcode is described as:

A perfect number is a positive integer that is equal to the sum of its proper divisors (positive divisors excluding itself). Given an integer n, return true if n is a perfect number, otherwise return false.

For example:

Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14

Approach 1: Basic Iteration through Divisors

The naive approach is to iterate through numbers from 1 to n-1 and sum up the divisors of n. Then, we can check if the sum is equal to n.

Here’s the Python code for this approach.

def checkPerfectNumber(num):
    if num <= 1:
        return False
    
    sum_divisors = 0
    for i in range(1, num):
        # If i is a divisor of num
        if num % i == 0:
            sum_divisors += i
    
    return sum_divisors == num

This approach is straightforward but not efficient. It has a time complexity of O(n) since we’re iterating through all numbers less than n.

Approach 2: Optimization by Reducing Search Space

We can optimize our search for divisors by noting that if d is a divisor of n, then n/d is also a divisor. Hence, we only need to search for divisors up to the square root of n.

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

This approach reduces the time complexity to O(√n), which is a significant improvement over the basic approach for large numbers.

Approach 3: Utilizing the Euclidean Formula for Perfect Numbers

Euclid proved that if 2^(p−1)(2^p − 1) is an integer, then it is a perfect number. Later, Euler proved that every even perfect number is of that form. This is known as the Euclidean Formula for perfect numbers. We can use this formula to check if a number is perfect without checking all its divisors.

def checkPerfectNumber(num):
    # The first six primes for Euclidean formula
    primes = [2, 3, 5, 7, 13, 17]
    
    for p in primes:
        perfect_number = (2 ** (p - 1)) * ((2 ** p) - 1)
        if perfect_number == num:
            return True
    
    return False

This approach has a constant time complexity, O(1), as it only checks a fixed number of perfect numbers derived from the Euclidean formula.

Conclusion

In this comprehensive article, we delved into the Perfect Number problem on Leetcode and explored three distinct approaches to solving it using Python. We began with the naive approach and iteratively optimized it. Ultimately, we employed a mathematical formula to achieve constant time complexity.