Perfect Number - Leetcode Solution

The Perfect Number problem on Leetcode is a straightforward problem that requires finding whether a given number is a perfect number or not. A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For example, 6 is a perfect number because its positive divisors (1, 2, 3) sum up to 6. In contrast, 10 is not a perfect number because its positive divisors (1, 2, 5) sum up to 8, which is not equal to 10.

The problem statement on Leetcode states the following:

A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. A divisor of an integer x is an integer that can divide x evenly.

Given an integer n, return true if n is a perfect number, otherwise false.

Example 1:

Input: n = 28 Output: true Explanation: 28 = 1 + 2 + 4 + 7 + 14, 1, 2, 4, 7, and 14 are all positive divisors of 28.

Example 2:

Input: n = 6 Output: true

Example 3:

Input: n = 496 Output: true

Example 4:

Input: n = 8128 Output: true

Example 5:

Input: n = 2 Output: false

Note:

1 <= num <= 10^8

Solution:

The most straightforward solution to this problem is to iterate through all possible divisors of the given number n and check whether the sum of divisors, excluding the number itself, is equal to n. To optimize the time complexity, we can stop iterating once we have found a divisor greater than the square root of the number n because any other divisor will have a corresponding divisor less than the square root, and we have already counted it.

Here's the code that implements this solution:

class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num == 1) return false;
        int sum = 1, i;
        for (i = 2; i * i < num; ++i) {
            if (num % i == 0) {
                sum += i;
                sum += num / i;
            }
        }
        if (i * i == num) sum += i;
        return sum == num;
    }
};

The code above first checks whether the number is 1 because 1 is not a perfect number. Next, it initializes a sum variable to 1 because 1 is always a divisor of any number, including itself. Then, it iterates through all possible divisors of the number n using a for loop that stops once the divisor is greater than the square root of the number n. Within this loop, it checks whether the current loop variable i is a divisor of the number n using the modulo operator. If so, it adds the divisor i and the corresponding dividend (num/i) to the sum variable. Once the loop completes, it checks whether the square of the loop variable i is equal to the number n (because it was not counted in the loop) and adds it to the sum if it is a divisor. Finally, the code returns true if the sum variable is equal to the number n and false otherwise.

This solution will run in O(sqrt(num)) time complexity, which is optimal for this problem.

1