# LeetCode 507: Perfect Number

## Problem Restatement

A positive integer is called a perfect number if the sum of its positive divisors excluding itself equals the number.

We are given an integer `num`.

We need to determine whether `num` is a perfect number.

The official problem defines a perfect number as a positive integer equal to the sum of all its positive divisors excluding itself. ([leetcode.com](https://leetcode.com/problems/perfect-number/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `num` |
| Output | `True` or `False` |
| Goal | Check whether `num` is perfect |

Function shape:

```python
class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        ...
```

## Examples

Example 1:

```python
num = 28
```

The positive divisors excluding `28` are:

```text
1, 2, 4, 7, 14
```

Their sum is:

```text
1 + 2 + 4 + 7 + 14 = 28
```

So the answer is:

```python
True
```

Example 2:

```python
num = 7
```

The divisors excluding `7` are:

```text
1
```

Their sum is:

```text
1
```

Since:

```text
1 != 7
```

the answer is:

```python
False
```

## First Thought: Check Every Divisor

A direct approach is to try every number from `1` to `num - 1`.

If a number divides `num`, add it to the sum.

```python
total = 0

for d in range(1, num):
    if num % d == 0:
        total += d
```

Finally:

```python
return total == num
```

This works, but it is inefficient for large numbers.

## Problem With Brute Force

The brute force solution checks almost every smaller number.

That costs:

```text
O(n)
```

However, divisors appear in pairs.

For example, if:

```text
28 % 2 == 0
```

then:

```text
28 / 2 = 14
```

So discovering divisor `2` also gives divisor `14`.

This means we only need to search up to:

```text
√num
```

## Key Insight

If:

```text
d divides num
```

then:

```text
num // d
```

is also a divisor.

Divisors come in symmetric pairs around the square root.

For example:

| Divisor | Paired divisor |
|---|---|
| 2 | 14 |
| 4 | 7 |

for:

```text
28
```

So we can find all divisors by checking only numbers from:

```text
2 to √num
```

The divisor `1` is always included for numbers greater than `1`.

## Algorithm

Handle small values first.

A perfect number must be positive and greater than `1`.

So:

```python
if num <= 1:
    return False
```

Initialize:

```python
total = 1
```

because `1` is always a divisor.

Then iterate:

```python
for d in range(2, int(num ** 0.5) + 1):
```

If `d` divides `num`:

1. Add `d`
2. Add its paired divisor `num // d`

Be careful with perfect squares.

If:

```text
d * d == num
```

then both divisors are the same, so add it only once.

Finally:

```python
return total == num
```

## Correctness

The algorithm checks every integer `d` from `2` to `√num`.

Whenever `d` divides `num`, both:

```text
d
```

and:

```text
num // d
```

are positive divisors of `num`.

Every divisor greater than `√num` is paired with a divisor smaller than `√num`, so no divisor is missed.

The divisor `1` is included separately at initialization.

For perfect squares, the square root divisor appears only once, and the algorithm correctly avoids double-counting it.

Therefore `total` equals the sum of all positive divisors excluding `num` itself.

The algorithm returns `True` exactly when this sum equals `num`, which matches the definition of a perfect number.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(√n)` | Only checks divisors up to the square root |
| Space | `O(1)` | Uses constant extra memory |

## Implementation

```python
class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num <= 1:
            return False

        total = 1

        limit = int(num ** 0.5)

        for d in range(2, limit + 1):
            if num % d == 0:
                total += d

                pair = num // d

                if pair != d:
                    total += pair

        return total == num
```

## Code Explanation

Numbers less than or equal to `1` cannot be perfect:

```python
if num <= 1:
    return False
```

The divisor `1` is always included:

```python
total = 1
```

We only check divisors up to the square root:

```python
limit = int(num ** 0.5)
```

If `d` divides `num`:

```python
if num % d == 0:
```

then `d` is a divisor:

```python
total += d
```

and its paired divisor is:

```python
pair = num // d
```

For non-square cases, add the paired divisor too:

```python
if pair != d:
    total += pair
```

Finally, compare the divisor sum with the original number:

```python
return total == num
```

## Testing

```python
def test_check_perfect_number():
    s = Solution()

    assert s.checkPerfectNumber(28) is True
    assert s.checkPerfectNumber(6) is True
    assert s.checkPerfectNumber(496) is True

    assert s.checkPerfectNumber(7) is False
    assert s.checkPerfectNumber(1) is False
    assert s.checkPerfectNumber(12) is False

    print("all tests passed")
```

Test meaning:

| Test | Why |
|---|---|
| `28` | Standard perfect number |
| `6` | Smallest perfect number |
| `496` | Larger known perfect number |
| `7` | Prime number case |
| `1` | Special invalid case |
| `12` | Ordinary composite number |