507. Perfect Number

We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.

Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.

Example:

Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14


Note: The input number n will not exceed 100,000,000. (1e8)

b'
\n\n

Solution

\n
\n

Approach #1 Brute Force [Time Limit Exceeded]

\n

Algorithm

\n

In brute force approach, we consider every possible number to be a divisor of the given number , by iterating over all the numbers lesser than . Then, we add up all the factors to check if the given number satisfies the Perfect Number property. This approach obviously fails if the number is very large.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . We iterate over all the numbers lesser than .

\n
• \n
• \n

Space complexity : . Constant extra space is used.

\n
• \n
\n
\n

Approach #2 Better Brute Force [Time Limit Exceeded]

\n

Algorithm

\n

We can little optimize the brute force by breaking the loop when the value of increase the value of . In that case, we can directly return .

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . In worst case, we iterate over all the numbers lesser than .

\n
• \n
• \n

Space complexity : . Constant extra space is used.

\n
• \n
\n
\n

Approach #3 Optimal Solution [Accepted]

\n

Algorithm

\n

In this method, instead of iterating over all the integers to find the factors of , we only iterate upto the . The reasoning behind this can be understood as follows.

\n

Consider the given number which can have distinct factors, namely . Now, since the number is divisible by , it is also divisible by i.e. . Also, the largest number in such a pair can only be up to (because ). Thus, we can get a significant reduction in the run-time by iterating only upto and considering such \'s and \'s in a single pass directly.

\n

Further, if is also a factor, we have to consider the factor only once while checking for the perfect number property.

\n

We sum up all such factors and check if the given number is a Perfect Number or not. Another point to be observed is that while considering 1 as such a factor, will also be considered as the other factor. Thus, we need to subtract from the .

\n\n

Complexity Analysis

\n
\n
• Time complexity : . We iterate only over the range .
• \n
• Space complexity : . Constant extra space is used.
• \n
\n
\n

Approach #4 Euclid-Euler Theorem [Accepted]

\n

Algorithm

\n

Euclid proved that is an even perfect number whenever is prime, where is prime.

\n

For example, the first four perfect numbers are generated by the formula , with a prime number, as follows:

\n
for p = 2:   21(22 \xe2\x88\x92 1) = 6\nfor p = 3:   22(23 \xe2\x88\x92 1) = 28\nfor p = 5:   24(25 \xe2\x88\x92 1) = 496\nfor p = 7:   26(27 \xe2\x88\x92 1) = 8128.\n
\n

Prime numbers of the form are known as Mersenne primes. For to be prime, it is necessary that itself be prime. However, not all numbers of the form with a prime are prime; for example, is not a prime number.

\n

You can see that for small value of , its related perfect number goes very high. So, we need to evaluate perfect numbers for some primes only, as for bigger prime its perfect number will not fit in 64 bits.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Number of primes will be in order .

\n
• \n
• \n

Space complexity : . Space used to store primes.

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'