# Perfect Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/perfect-number)
Canonical: https://scaleengineer.com/dsa/problems/perfect-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Grammarly](https://scaleengineer.com/companies/grammarly)
---
## Problem
A [**perfect number**](https://en.wikipedia.org/wiki/Perfect%5Fnumber) is a **positive integer** that is equal to the sum of its **positive divisors**, excluding the number itself. A **divisor** of an integer `x` is an integer that can divide `x` evenly.

Given an integer `n`, return `true` _if_ `n` _is a perfect number, otherwise return_ `false`.

**Example 1:**

**Input:** num = 28
**Output:** true
**Explanation:** 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.

**Example 2:**

**Input:** num = 7
**Output:** false

**Constraints:**

* `1 <= num <= 108`

# Approaches
## Brute Force Iteration
This approach directly follows the definition of a perfect number. We iterate through all possible divisors of `num` from 1 up to `num - 1`. For each number in this range, we check if it divides `num` evenly. If it does, we add it to a running sum. Finally, after checking all numbers, we compare this sum with the original number `num`. If they are equal, `num` is a perfect number.
**Time:** O(n) - The loop runs from 1 to `num - 1`, so the number of operations is directly proportional to `num`. For the given constraint of `num <= 10^8`, this approach will be too slow and likely result in a 'Time Limit Exceeded' error. · **Space:** O(1) - We only use a few variables (`sum`, `i`) to store intermediate values, regardless of the size of `num`. The space required is constant.
**Pros:** Simple to understand and implement.; Directly translates the mathematical definition into code.
**Cons:** Highly inefficient for large values of `num`.; Will not pass the time limits for the given constraints.
### Explanation
```java
class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num <= 1) {
            return false;
        }
        int sum = 0;
        for (int i = 1; i < num; i++) {
            if (num % i == 0) {
                sum += i;
            }
        }
        return sum == num;
    }
}
```
### Algorithm
*   First, handle the edge case where `num <= 1`. Since perfect numbers are positive integers greater than 1, return `false`.
*   Initialize a variable `sum` to 0 to store the sum of the divisors.
*   Iterate with a loop variable `i` from 1 up to `num - 1`.
*   Inside the loop, use the modulo operator (`%`) to check if `i` is a divisor of `num` (i.e., `num % i == 0`).
*   If `i` is a divisor, add it to `sum`.
*   After the loop completes, compare `sum` with `num`. If they are equal, it means `num` is a perfect number, so return `true`. Otherwise, return `false`.

## Optimized Iteration up to Square Root
This approach improves upon the brute-force method by recognizing that divisors come in pairs. If `i` is a divisor of `num`, then `num / i` is also a divisor. We only need to iterate up to the square root of `num`. For each divisor `i` we find, we add both `i` and its corresponding pair `num / i` to the sum. This significantly reduces the number of iterations required.
**Time:** O(sqrt(n)) - The loop runs from 2 up to the square root of `num`. This is a significant improvement over the O(n) approach and is efficient enough to pass the time limits for `num <= 10^8`. · **Space:** O(1) - Similar to the brute-force approach, the space used is constant as it does not depend on the input size.
**Pros:** Much more efficient than the brute-force approach.; Passes the time constraints of the problem.
**Cons:** Slightly more complex logic due to handling divisor pairs and the perfect square case.
### Explanation
```java
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 * i != num) {
                    sum += num / i;
                }
            }
        }
        return sum == num;
    }
}
```
### Algorithm
*   Handle the edge case: if `num <= 1`, it cannot be a perfect number, so return `false`.
*   Initialize a variable `sum` to 1. We pre-add 1 as it's a divisor for all `num > 1`. This allows us to start the loop from 2.
*   Iterate with a loop variable `i` from 2 up to `sqrt(num)` (i.e., `i * i <= num`).
*   Inside the loop, check if `i` is a divisor of `num` (`num % i == 0`).
*   If it is, add `i` to the `sum`. We also need to add its pair, `num / i`.
*   A special case arises if `num` is a perfect square. In this case, `i` and `num / i` are the same. To avoid adding the square root twice, we only add `num / i` if `i * i != num`.
*   After the loop, compare the final `sum` with `num`.

## Euclid-Euler Theorem (Hardcoded Values)
This is a mathematical approach that leverages the Euclid-Euler theorem. The theorem provides a formula for all known (even) perfect numbers: `2^(p-1) * (2^p - 1)`, where `p` is a prime and `2^p - 1` is a Mersenne prime. Given the constraint `num <= 10^8`, we can pre-calculate all perfect numbers that fall within this range. There are only five such numbers: 6, 28, 496, 8128, and 33550336. The problem then reduces to simply checking if the input `num` is one of these five values.
**Time:** O(1) - The solution involves a fixed number of comparisons, regardless of the input `num`. This is the most efficient time complexity possible. · **Space:** O(1) - No extra space is used that scales with the input. The storage for the hardcoded numbers is constant.
**Pros:** Extremely fast and efficient.; Simple and clean implementation.
**Cons:** Relies on pre-existing mathematical knowledge (Euclid-Euler theorem).; The solution is specific to the given constraints; if the constraints were much larger, this approach would require pre-calculating more perfect numbers.
### Explanation
```java
class Solution {
    public boolean checkPerfectNumber(int num) {
        // The known perfect numbers within the constraint 1 <= num <= 10^8
        // are 6, 28, 496, 8128, and 33550336.
        switch (num) {
            case 6:
            case 28:
            case 496:
            case 8128:
            case 33550336:
                return true;
            default:
                return false;
        }
    }
}
```
### Algorithm
*   Identify all perfect numbers up to the constraint `10^8` using the Euclid-Euler theorem.
    *   For p=2: `2^1 * (2^2 - 1) = 6`
    *   For p=3: `2^2 * (2^3 - 1) = 28`
    *   For p=5: `2^4 * (2^5 - 1) = 496`
    *   For p=7: `2^6 * (2^7 - 1) = 8128`
    *   For p=13: `2^12 * (2^13 - 1) = 33550336`
*   Since it is an open mathematical problem whether any odd perfect numbers exist, we can safely assume for this problem that we only need to consider these five even perfect numbers.
*   Implement a check, for instance using a `switch` statement, to see if the input `num` matches any of these five pre-calculated values.
*   Return `true` if a match is found, and `false` otherwise.

# Solutions
### Java

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

```

### Python

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

```

### CPP

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

```