LeetCode 507: Perfect Number Solution in Python – A Step-by-Step Guide

What Is LeetCode 507: Perfect Number?

In LeetCode 507: Perfect Number, you’re given a positive integer, and your task is to determine if it’s a perfect number. A perfect number is one where the sum of its proper divisors (all positive divisors except the number itself) equals the number. For example, 6 is perfect (1 + 2 + 3 = 6), but 15 is not (1 + 3 + 5 = 9 ≠ 15). This problem tests your ability to work with divisors, related to concepts in LeetCode 204: Count Primes.

Problem Statement

• Input: Integer num (positive).
• Output: Boolean—True if perfect, False otherwise.
• Rules: Sum only proper divisors (exclude num); num is positive.

Constraints

• 1 <= num <= 10⁸

Examples

• Input: 28
• Output: True
• Divisors: 1, 2, 4, 7, 14 → 1 + 2 + 4 + 7 + 14 = 28.
• Input: 7
• Output: False
• Divisors: 1 → 1 ≠ 7.
• Input: 1
• Output: False
• No proper divisors → 0 ≠ 1.

Understanding the Problem: Seeking Perfection

To solve LeetCode 507: Perfect Number in Python, we need a function that finds all proper divisors of a number and checks if their sum equals the number. A naive approach might test every number up to num, but with inputs up to 10⁸, we need efficiency. We’ll explore:

• Best Solution (Optimized with Square Root): O(√n) time, O(1) space—fast and smart.
• Alternative Solution (Brute Force): O(n) time, O(1) space—simpler but slower.

Let’s dive into the optimized solution with a friendly breakdown!

Best Solution: Optimized Divisor Sum with Square Root

Why the Square Root Approach Wins

The optimized solution using the square root is the best for LeetCode 507 because it’s efficient—O(√n) time and O(1) space. Instead of checking all numbers up to num, it only checks up to √n, pairing divisors (e.g., 1 and 28 for 28) to sum them quickly. It’s like finding half the puzzle pieces and knowing the other half match perfectly!

How It Works

Think of this as a divisor treasure hunt:

• Step 1: Edge Case:
• If num ≤ 1, return False (1 has no proper divisors).
• Step 2: Sum Divisors:
• Start sum at 1 (1 is always a divisor).
• Check numbers from 2 to √n.
• If i divides num, add i and num // i (unless i = num // i).
• Step 3: Check Perfection:
• Compare sum to num.
• Why It Works:
• Divisors come in pairs (e.g., 2 and 14 for 28).
• √n limits the search, covering all pairs.

It’s like a speedy divisor roundup!

Step-by-Step Example

Example: 28

• Init: num = 28, sum = 1 (1 is a divisor).
• Step 1: num > 1, proceed.
• Step 2: Check up to √28 ≈ 5:
• i = 2: 28 % 2 = 0, add 2 and 28 // 2 = 14, sum = 1 + 2 + 14 = 17.
• i = 3: 28 % 3 ≠ 0, skip.
• i = 4: 28 % 4 = 0, add 4 and 28 // 4 = 7, sum = 17 + 4 + 7 = 28.
• i = 5: 28 % 5 ≠ 0, skip.
• Step 3: sum = 28, num = 28, True.

Example: 7

• Init: sum = 1.
• Step 1: num > 1.
• Step 2: √7 ≈ 2:
• i = 2: 7 % 2 ≠ 0, skip.
• Step 3: sum = 1, num = 7, False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        # Step 1: Handle edge cases
        if num <= 1:
            return False

        # Step 2: Start sum with 1
        divisor_sum = 1

        # Step 3: Check divisors up to sqrt(num)
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:  # i is a divisor
                divisor_sum += i
                # Add the pair divisor if different
                if i != num // i:
                    divisor_sum += num // i

        # Step 4: Check if perfect
        return divisor_sum == num

• Lines 4-5: If num ≤ 1, not perfect (no proper divisors).
• Line 8: Start sum with 1 (always a divisor).
• Line 11: Loop from 2 to √n (inclusive).
• Lines 12-15: If i divides num:
• Add i.
• Add num // i unless it’s the same (e.g., 4 for 16).
• Line 18: Sum equals num → perfect.
• Time Complexity: O(√n)—check up to square root.
• Space Complexity: O(1)—just a variable.

It’s like a perfect number detector!

Alternative Solution: Brute Force Divisor Check

Why an Alternative Approach?

The brute-force solution checks all numbers from 1 to num-1 to find divisors and sum them. It’s O(n) time and O(1) space—simple to understand but inefficient for large numbers like 10⁸. Great for grasping the basics before optimizing.

How It Works

Picture this as a full divisor sweep:

• Step 1: If num ≤ 1, return False.
• Step 2: Sum all numbers from 1 to num-1 that divide num.
• Step 3: Check if sum equals num.

It’s like counting every possible helper!

Step-by-Step Example

Example: 6

• Init: sum = 0.
• Step 1: num > 1.
• Step 2: Check 1 to 5:
• 6 % 1 = 0, sum = 1.
• 6 % 2 = 0, sum = 3.
• 6 % 3 = 0, sum = 6.
• 6 % 4 ≠ 0, skip.
• 6 % 5 ≠ 0, skip.
• Step 3: sum = 6, num = 6, True.

Code for Brute Force

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

        divisor_sum = 0
        for i in range(1, num):
            if num % i == 0:
                divisor_sum += i

        return divisor_sum == num

• Time Complexity: O(n)—check all up to num-1.
• Space Complexity: O(1)—just the sum.

It’s a slow but sure checker!

Comparing the Two Solutions

• Optimized (Best):
• Pros: O(√n), efficient.
• Cons: Slightly trickier logic.
• Brute Force (Alternative):
• Pros: O(n), super simple.
• Cons: Too slow for big numbers.

Optimized wins big!

Additional Examples and Edge Cases

• 496: False (1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 = 496).
• 2: False (1 ≠ 2).
• 33550336: True (perfect number).

Optimized handles them all!

Complexity Recap

• Optimized: Time O(√n), Space O(1).
• Brute Force: Time O(n), Space O(1).

Optimized is the efficiency star!

Key Takeaways

• Square Root: Cuts time—learn at Python Basics!
• Divisors: Pairs save effort.
• Perfect Numbers: Rare and cool.
• Math: Fun in code!

Final Thoughts: Find Perfection!

LeetCode 507: Perfect Number in Python is a delightful number theory challenge. The square root optimization makes it fast, while brute force keeps it simple. Want more? Try LeetCode 204: Count Primes or LeetCode 367: Valid Perfect Square. Ready to hunt perfect numbers? Head to Solve LeetCode 507 on LeetCode and check for perfection today!