Code Implementation

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num <= 1:
            return False
        divisors_sum = 1
        i = 2
        while i * i <= num:
            if num % i == 0:
                divisors_sum += i
                if i != num // i:
                    divisors_sum += num // i
            i += 1
        return divisors_sum == num
    

class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num <= 1) return false;
        int sum = 1;
        for (int i = 2; i * i <= num; ++i) {
            if (num % i == 0) {
                sum += i;
                if (i != num / i) sum += num / i;
            }
        }
        return sum == num;
    }
};
    

class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num <= 1) return false;
        int sum = 1;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                sum += i;
                if (i != num / i) sum += num / i;
            }
        }
        return sum == num;
    }
}
    

var checkPerfectNumber = function(num) {
    if (num <= 1) return false;
    let sum = 1;
    for (let i = 2; i * i <= num; i++) {
        if (num % i === 0) {
            sum += i;
            if (i !== num / i) sum += num / i;
        }
    }
    return sum === num;
};
    

Problem Description

You are given an integer num. Your task is to determine whether num is a perfect number.

A perfect number is a positive integer that is equal to the sum of all its positive divisors except itself. For example, 28 is a perfect number because its divisors (excluding itself) are 1, 2, 4, 7, and 14, and their sum is 28.

• The input is a single positive integer num.
• Return true if num is perfect, otherwise false.
• You must not count num itself as one of its divisors.
• Constraints: 1 <= num <= 10^8

Thought Process

To solve this problem, we need to check if the sum of all divisors of num (excluding num itself) equals num. The most straightforward way is to find all numbers from 1 up to num-1 that divide num and sum them. However, this is inefficient for large values of num because it requires checking up to 10^8 numbers.

To optimize, we realize that divisors come in pairs. For any divisor i of num, num / i is also a divisor. For example, if 2 divides 28, then 14 also divides 28, and 2 * 14 = 28. By only iterating up to the square root of num, we can find all divisor pairs efficiently.

We must be careful not to count num itself or duplicate divisors (like for perfect squares).

Solution Approach

• Step 1: Handle special cases. If num is less than or equal to 1, it's not perfect (since its only divisor is itself).
• Step 2: Initialize a variable (e.g., sum) to 1, because 1 is a divisor of every number except itself.
• Step 3: Loop from 2 up to the square root of num (inclusive). For each i in this range:
  • If i divides num (i.e., num % i == 0), add i to sum.
  • Also add num / i to sum if i is not equal to num / i (to avoid double-counting square roots).
• Step 4: After the loop, check if sum equals num. If so, return true; otherwise, return false.

This approach is efficient because it only requires checking up to the square root of num, making it feasible even for large inputs (up to 10^8).

Example Walkthrough

Let's use num = 28 as an example:

• Initialize sum = 1.
• Loop i from 2 to 5 (since sqrt(28) ≈ 5.29):
• i = 2: 28 % 2 == 0. Add 2 and 14 (28/2) to sum. sum = 1 + 2 + 14 = 17.
• i = 3: 28 % 3 != 0. Skip.
• i = 4: 28 % 4 == 0. Add 4 and 7 (28/4) to sum. sum = 17 + 4 + 7 = 28.
• i = 5: 28 % 5 != 0. Skip.
• Now sum = 28, which equals the original number, so 28 is a perfect number.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n), since we check all numbers from 1 to num-1.
  • Space Complexity: O(1), as we only use a sum variable.
• Optimized approach (current solution):
  • Time Complexity: O(√n), because we only loop up to the square root of num.
  • Space Complexity: O(1), as we only store a sum and loop variables.

The optimized approach is much faster for large values of num.

Summary

To determine if a number is perfect, we efficiently sum its proper divisors by leveraging the fact that divisors come in pairs and only need to check up to the square root of the number. This reduces the time from linear to square root, making the solution practical for large inputs. The key insight is to avoid redundant checks and double-counting, resulting in a simple yet powerful algorithm.