Problem Description

A perfect number is a positive integer that equals the sum of all its positive divisors, excluding itself. A divisor of an integer x is any integer that can divide x without leaving a remainder.

For example, consider the number 6:

• Its divisors are: 1, 2, 3, and 6
• Excluding 6 itself, the sum is: 1 + 2 + 3 = 6
• Since this sum equals the original number, 6 is a perfect number

Another example is 28:

• Its divisors are: 1, 2, 4, 7, 14, and 28
• Excluding 28 itself, the sum is: 1 + 2 + 4 + 7 + 14 = 28
• Therefore, 28 is also a perfect number

Given an integer n, determine whether it is a perfect number. Return true if n is a perfect number, otherwise return false.

The solution works by iterating through potential divisors from 2 up to the square root of num. For each divisor i found, both i and its corresponding quotient num // i are added to the sum (avoiding duplication when i equals num // i). The initial sum starts at 1 since 1 is always a divisor. Special handling is needed for the case when num is 1, which returns false immediately since 1 has no proper divisors other than itself.

Intuition

To check if a number is perfect, we need to find all its divisors and sum them up (excluding the number itself). The straightforward approach would be to check every number from 1 to num-1, but this would be inefficient for large numbers.

The key insight is that divisors always come in pairs. When we divide num by a divisor i, we get another divisor num // i. For example, if 12 is divisible by 3, then 12/3 = 4 is also a divisor. This means we only need to check numbers up to the square root of num.

Why stop at the square root? Because once i exceeds √num, the quotient num // i will be less than i, meaning we've already found this divisor pair from the other direction. The condition i <= num // i is equivalent to i <= √num but avoids potential floating-point precision issues.

We start our sum at 1 because 1 is always a divisor of any positive integer. Then we iterate from 2 upwards, and for each divisor i we find, we add both i and num // i to our sum. We need to be careful not to double-count when i equals num // i (which happens when num is a perfect square and i is its square root).

The special case of num = 1 needs separate handling because 1's only divisor is itself, making the sum of proper divisors equal to 0, not 1. Therefore, 1 cannot be a perfect number by definition.

Learn more about Math patterns.

Solution Approach

The implementation follows the enumeration approach to find all divisors efficiently:

1. Special Case Handling: First check if num is 1. Since 1 has no proper divisors other than itself, it cannot be a perfect number, so we return false.

2. Initialize Variables:

   • Set s = 1 to start with 1 as a divisor (since 1 divides every positive integer)
   • Set i = 2 as our starting point for checking other divisors

3. Iterate Through Potential Divisors: Use a while loop with condition i <= num // i (equivalent to i <= √num):

   • For each i, check if it divides num evenly using the modulo operator: num % i == 0
   • If i is a divisor:
     • Add i to the sum s
     • Calculate the corresponding divisor num // i
     • If i != num // i (to avoid double-counting when num is a perfect square), also add num // i to the sum
   • Increment i to check the next potential divisor

4. Check Result: After finding all divisors and computing their sum, return whether s == num.

The algorithm's efficiency comes from only checking divisors up to √num instead of all numbers up to num - 1. This reduces the time complexity from O(n) to O(√n).

For example, with num = 28:

• Start with s = 1, i = 2
• i = 2: 28 % 2 = 0, so add 2 and 14 (28/2), s = 1 + 2 + 14 = 17
• i = 3: 28 % 3 ≠ 0, skip
• i = 4: 28 % 4 = 0, so add 4 and 7 (28/4), s = 17 + 4 + 7 = 28
• i = 5: Now 5 > 28/5, loop ends
• Return s == 28, which is true

Example Walkthrough

Let's walk through the algorithm with num = 12 to see how it identifies that 12 is not a perfect number.

Step 1: Special Case Check

• Is num == 1? No, so we continue.

Step 2: Initialize Variables

• s = 1 (since 1 is always a divisor)
• i = 2 (start checking from 2)

Step 3: Find Divisors

Iteration 1: i = 2

• Check condition: 2 <= 12 // 2 → 2 <= 6 ✓
• Is 12 divisible by 2? 12 % 2 = 0 ✓
• Add i to sum: s = 1 + 2 = 3
• Calculate pair: 12 // 2 = 6
• Since 2 ≠ 6, also add 6: s = 3 + 6 = 9
• Increment: i = 3

Iteration 2: i = 3

• Check condition: 3 <= 12 // 3 → 3 <= 4 ✓
• Is 12 divisible by 3? 12 % 3 = 0 ✓
• Add i to sum: s = 9 + 3 = 12
• Calculate pair: 12 // 3 = 4
• Since 3 ≠ 4, also add 4: s = 12 + 4 = 16
• Increment: i = 4

Iteration 3: i = 4

• Check condition: 4 <= 12 // 4 → 4 <= 3 ✗
• Loop terminates

Step 4: Check Result

• Sum of divisors (excluding 12): s = 16
• The divisors we found were: 1, 2, 3, 4, 6
• Is s == num? Is 16 == 12? No
• Return false

To verify: The divisors of 12 are indeed 1, 2, 3, 4, 6, and 12. Excluding 12 itself, their sum is 1 + 2 + 3 + 4 + 6 = 16, which is not equal to 12, confirming that 12 is not a perfect number.

Solution Implementation

Time and Space Complexity

The time complexity is O(√n), where n is the value of num. This is because the loop iterates while i <= num // i, which is equivalent to i² <= num or i <= √num. The loop starts from i = 2 and increments by 1 each iteration until it reaches approximately √num, resulting in O(√n) iterations. Each iteration performs constant time operations (modulo check, additions, and comparisons).

The space complexity is O(1). The algorithm only uses a fixed amount of extra space for the variables s (sum accumulator) and i (loop counter), regardless of the input size. No additional data structures that scale with the input are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Missing Edge Case for num = 1

One of the most common mistakes is forgetting to handle the edge case when num = 1. Without this check, the algorithm would return True for 1 since the sum of its divisors (excluding itself) would be 0, and the initial divisor_sum = 1 would never get updated, incorrectly identifying 1 as a perfect number.

Solution: Always include the check if num == 1: return False at the beginning of the function.

2. Double-Counting Square Root Divisors

When num is a perfect square, failing to check if i != num // i will cause the square root to be added twice to the sum. For example, if num = 36 and i = 6, both 6 and 36/6=6 would be added, incorrectly inflating the sum.

Solution: Always verify that i != num // i before adding the complementary divisor to avoid double-counting.

3. Including the Number Itself in the Sum

A critical error is accidentally including num in the divisor sum. This happens when the loop condition or divisor collection logic isn't properly bounded. For instance, if checking divisors up to num instead of sqrt(num), or if the complementary divisor num // i equals num when i = 1.

Solution: Start the loop from i = 2 (not 1) and ensure the loop condition prevents reaching divisors that would yield num as the complementary divisor.

4. Incorrect Loop Boundary

Using i < num // i instead of i <= num // i (or equivalently i * i <= num) will miss some divisor pairs. For example, with num = 16, using i < num // i would stop before checking i = 4, missing the divisor 4.

Solution: Use i * i <= num or i <= num // i to ensure all divisor pairs are checked, including when i equals the square root.

5. Integer Overflow with Large Numbers

When using i * i <= num as the loop condition, for very large values of num, i * i might cause integer overflow in some programming languages.

Solution: Use i <= num // i instead of i * i <= num to avoid potential overflow issues while maintaining the same logic.