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

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

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

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

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

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

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

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

Approach #4 Euclid-Euler Theorem [Accepted]

Algorithm

Euclid proved that $$2^{p−1}(2^p − 1)$$ is an even perfect number whenever $$2^p − 1$$ is prime, where $$p$$ is prime.

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

for p = 2:   21(22 − 1) = 6
for p = 3:   22(23 − 1) = 28
for p = 5:   24(25 − 1) = 496
for p = 7:   26(27 − 1) = 8128.

Prime numbers of the form $$2^p − 1$$ are known as Mersenne primes. For $$2^p − 1$$ to be prime, it is necessary that $$p$$ itself be prime. However, not all numbers of the form $$2^p − 1$$ with a prime $$p$$ are prime; for example, $$2^{11} − 1 = 2047 = 23 × 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

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

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

Analysis written by: @vinod23