507. Perfect Number

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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:

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.
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
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
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

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

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

1class Solution:
2    def checkPerfectNumber(self, num: int) -> bool:
3        # A perfect number is a positive integer equal to the sum of its positive divisors, excluding itself
4        # Edge case: 1 is not a perfect number (has no proper divisors)
5        if num == 1:
6            return False
7      
8        # Initialize sum with 1 (since 1 is always a divisor)
9        divisor_sum = 1
10      
11        # Start checking from 2 up to sqrt(num)
12        i = 2
13      
14        # Iterate only up to sqrt(num) for efficiency
15        while i * i <= num:
16            # Check if i is a divisor of num
17            if num % i == 0:
18                # Add the divisor to sum
19                divisor_sum += i
20              
21                # Add the corresponding pair divisor (num/i) if it's different from i
22                # This avoids adding the same divisor twice when i = sqrt(num)
23                if i != num // i:
24                    divisor_sum += num // i
25          
26            i += 1
27      
28        # Check if sum of all proper divisors equals the number itself
29        return divisor_sum == num
30

1class Solution {
2    /**
3     * Checks if a given number is a perfect number.
4     * A perfect number is a positive integer that equals the sum of its positive divisors,
5     * excluding the number itself.
6     * 
7     * @param num The number to check
8     * @return true if num is a perfect number, false otherwise
9     */
10    public boolean checkPerfectNumber(int num) {
11        // Edge case: 1 is not a perfect number (has no proper divisors except itself)
12        if (num == 1) {
13            return false;
14        }
15      
16        // Initialize sum with 1 (since 1 is always a divisor of any number > 1)
17        int sumOfDivisors = 1;
18      
19        // Iterate through potential divisors up to sqrt(num)
20        // We only need to check up to sqrt(num) for efficiency
21        for (int divisor = 2; divisor * divisor <= num; divisor++) {
22            // Check if current number is a divisor
23            if (num % divisor == 0) {
24                // Add the divisor to the sum
25                sumOfDivisors += divisor;
26              
27                // Add the corresponding pair divisor (num/divisor)
28                // But avoid adding the same divisor twice when divisor = sqrt(num)
29                if (divisor != num / divisor) {
30                    sumOfDivisors += num / divisor;
31                }
32            }
33        }
34      
35        // A perfect number equals the sum of its proper divisors
36        return sumOfDivisors == num;
37    }
38}
39

1class Solution {
2public:
3    bool checkPerfectNumber(int num) {
4        // A perfect number is a positive integer that equals the sum of its positive divisors, excluding itself
5        // Example: 6 = 1 + 2 + 3, so 6 is a perfect number
6      
7        // Edge case: 1 is not a perfect number (only divisor is 1 itself)
8        if (num == 1) {
9            return false;
10        }
11      
12        // Initialize sum with 1 (1 is always a divisor for any number > 1)
13        int divisorSum = 1;
14      
15        // Iterate from 2 to sqrt(num) to find all divisors efficiently
16        // We only need to check up to sqrt(num) because divisors come in pairs
17        for (int divisor = 2; divisor * divisor <= num; ++divisor) {
18            // Check if current number is a divisor
19            if (num % divisor == 0) {
20                // Add the divisor to sum
21                divisorSum += divisor;
22              
23                // Add the corresponding pair divisor (num/divisor)
24                // But avoid adding the same divisor twice when divisor == num/divisor (perfect square case)
25                if (divisor != num / divisor) {
26                    divisorSum += num / divisor;
27                }
28            }
29        }
30      
31        // Check if sum of all proper divisors equals the number itself
32        return divisorSum == num;
33    }
34};
35

1/**
2 * Checks if a number is a perfect number
3 * A perfect number is a positive integer that equals the sum of its positive divisors, excluding itself
4 * @param num - The number to check
5 * @returns true if num is a perfect number, false otherwise
6 */
7function checkPerfectNumber(num: number): boolean {
8    // Perfect numbers must be greater than 1
9    if (num <= 1) {
10        return false;
11    }
12  
13    // Initialize sum with 1 (since 1 is always a divisor)
14    let divisorSum: number = 1;
15  
16    // Iterate through potential divisors up to sqrt(num)
17    // We only need to check up to sqrt(num) for efficiency
18    for (let divisor: number = 2; divisor * divisor <= num; divisor++) {
19        // Check if current number is a divisor
20        if (num % divisor === 0) {
21            // Add the divisor to sum
22            divisorSum += divisor;
23          
24            // Add the corresponding pair divisor (num/divisor) if it's different
25            // This avoids double-counting when divisor equals sqrt(num)
26            if (divisor * divisor !== num) {
27                divisorSum += num / divisor;
28            }
29        }
30    }
31  
32    // Check if sum of divisors equals the original number
33    return divisorSum === num;
34}
35

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.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan: