This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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

**Example:**

Input:28Output:TrueExplanation:28 = 1 + 2 + 4 + 7 + 14

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

b'

\n## Solution

\n

\n#### Approach #1 Brute Force [Time Limit Exceeded]

\n

\n#### Approach #2 Better Brute Force [Time Limit Exceeded]

\n

\n#### Approach #3 Optimal Solution [Accepted]

\n

\n#### Approach #4 Euclid-Euler Theorem [Accepted]

\n\n

\n

'
\n\n

\n\n

**Algorithm**

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
Time complexity : . We iterate over all the numbers lesser than .

\n \n - \n
Space complexity : . Constant extra space is used.

\n \n

\n

**Algorithm**

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
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

**Algorithm**

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.

\nConsider 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.

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

\nWe 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
- Time complexity : . We iterate only over the range . \n
- Space complexity : . Constant extra space is used. \n

\n

**Algorithm**

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

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

\nfor 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

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.

\nYou 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
Time complexity : . Number of primes will be in order .

\n \n - \n
Space complexity : . Space used to store primes.

\n \n

\n

Analysis written by: @vinod23

\n