Perfect Number

Given an integer N, determine whether it is a Perfect Number or not. Return true if it is a Perfect Number, otherwise return false.

A Perfect Number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself.

Brute Force Approach

The first observation is very direct: every proper divisor of N must lie between 1 and N - 1. So one simple way to solve the problem is to check every number in that range and collect the ones that divide N exactly.

The next observation is that a number should be added to the divisor sum only when it leaves remainder 0. Once that is clear, the full idea becomes straightforward: walk through all possible proper divisors, keep adding the valid ones, and finally compare the sum with N.

Algorithm

• Start with a variable sum as 0, because no proper divisor has been added yet. This variable will store the total of all valid divisors found so far.

• Check every number from 1 to N - 1, because the number itself must not be included in the sum of proper divisors.

• For each number i, test whether N % i == 0. That check is necessary because only exact divisors should contribute to the sum.

• Whenever i divides N exactly, add i to sum. This builds the total of all proper divisors one by one.

• After all possible divisors have been checked, compare sum with N. If both are equal, return true; otherwise, return false.

Key Points

• If N <= 1, the answer is always false because a Perfect Number must be positive and must have proper divisors that can sum back to it.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N), because every number from 1 to N - 1 may be checked.

Space Complexity: O(1), because only a few variables are used.

Optimal Approach

The important observation here is that divisors usually come in pairs. If i divides N, then N / i also divides N. For example, for 28, the pairs are (1, 28), (2, 14), and (4, 7).

That means checking all numbers up to N - 1 is unnecessary. Only the smaller side of each pair needs to be searched, which means checking up to sqrt(N) is enough. Whenever one divisor is found, its paired divisor can also be added immediately. The only careful case is a perfect square, where both values in the pair become the same and should be added only once.

Algorithm

• First, handle the case N <= 1 by returning false, because such numbers cannot be Perfect Numbers.

• Start the divisor sum with 1, because 1 is always a proper divisor of every number greater than 1, and it should be included from the beginning.

• Check every number i starting from 2 while i * i <= N. This limit matters because any larger divisor would already have a smaller paired divisor.

• If i divides N, add its contribution to the sum. In the normal case, both i and N / i should be added because both are proper divisors.

• Before adding both values, check whether i * i == N. If that happens, only add i once, because the pair has collapsed into the same divisor.

• After all divisor pairs have been processed, compare the final sum with N. If both are equal, return true; otherwise, return false.

Key Points

• N = 1 is not a Perfect Number.

• For a perfect square, the square root divisor must be added only once.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(sqrt(N)), because only divisors up to the square root are checked.

Space Complexity: O(1), because no extra data structure is needed.