Solution

Approach #1 Brute Force [Time Limit Exceeded]

Algorithm

In brute force approach, we consider every possible number to be a divisor of the given number $$num$$ , by iterating over all the numbers lesser than $$num$$ . 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 $$num$$ is very large.

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ . We iterate over all the numbers lesser than $$n$$ .

  \n
\n
• \n

  Space complexity : $$O(1)$$ . Constant extra space is used.

  \n
\n

Approach #2 Better Brute Force [Time Limit Exceeded]

Algorithm

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

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ . In worst case, we iterate over all the numbers lesser than $$n$$ .

  \n
\n
• \n

  Space complexity : $$O(1)$$ . Constant extra space is used.

  \n
\n

Approach #3 Optimal Solution [Accepted]

Algorithm

In this method, instead of iterating over all the integers to find the factors of $$num$$ , we only iterate upto the $$\\sqrt{n}$$ . The reasoning behind this can be understood as follows.

Consider the given number $$num$$ which can have $$m$$ distinct factors, namely $$n_1, n_2,..., n_m$$ . Now, since the number $$num$$ is divisible by $$n_i$$ , it is also divisible by $$n_j=num/n_1$$ i.e. $$n_i*n_j=num$$ . Also, the largest number in such a pair can only be up to $$\\sqrt{num}$$ (because $$\\sqrt{num} \\times \\sqrt{num}=num$$ ). Thus, we can get a significant reduction in the run-time by iterating only upto $$\\sqrt{num}$$ and considering such $$n_i$$ \'s and $$n_j$$ \'s in a single pass directly.

Further, if $$\\sqrt{num}$$ is also a factor, we have to consider the factor only once while checking for the perfect number property.

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, $$num$$ will also be considered as the other factor. Thus, we need to subtract $$num$$ from the $$sum$$ .

Complexity Analysis

\n
• Time complexity : $$O(\\sqrt{n})$$ . We iterate only over the range $$1 < i &leq; \\sqrt{num}$$ .
\n
• Space complexity : $$O(1)$$ . Constant extra space is used.
\n

Approach #4 Euclid-Euler Theorem [Accepted]

Algorithm

Euclid proved that $$2^{p\xe2\x88\x921}(2^p \xe2\x88\x92 1)$$ is an even perfect number whenever $$2^p \xe2\x88\x92 1$$ is prime, where $$p$$ is prime.

For example, the first four perfect numbers are generated by the formula $$2^{p\xe2\x88\x921}(2^p \xe2\x88\x92 1)$$ , with $$p$$ a prime number, as follows:

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

Prime numbers of the form $$2^p \xe2\x88\x92 1$$ are known as Mersenne primes. For $$2^p \xe2\x88\x92 1$$ to be prime, it is necessary that $$p$$ itself be prime. However, not all numbers of the form $$2^p \xe2\x88\x92 1$$ with a prime $$p$$ are prime; for example, $$2^{11} \xe2\x88\x92 1 = 2047 = 23 \xc3\x97 89$$ is not a prime number.

You can see that for small value of $$p$$ , its related perfect number goes very high. So, we need to evaluate perfect numbers for some primes $$(2, 3, 5, 7, 13, 17, 19, 31)$$ only, as for bigger prime its perfect number will not fit in 64 bits.

Complexity Analysis

\n
• \n

  Time complexity : $$O(\\log{n})$$ . Number of primes will be in order $$\\log{num}$$ .

  \n
\n
• \n

  Space complexity : $$O(\\log{n})$$ . Space used to store primes.

  \n
\n

Analysis written by: @vinod23