LeetCode 507: Perfect Number

Explanation

To determine if a number is a perfect number, we need to find all the divisors of the number (excluding the number itself) and check if the sum of these divisors equals the number. We can optimize this process by iterating only up to the square root of the number and considering pairs of divisors. If we find a pair of divisors that multiply together to equal the number, we can add both divisors to the sum.

Algorithm:

1. Initialize sum as 1 (since 1 is always a divisor).
2. Iterate from 2 to the square root of the number:
   • If the current number i divides the given number n:
     • Add i and n/i to the sum.
3. Check if the sum equals n. If it does, return true (perfect number), otherwise return false.

Time Complexity

The time complexity of this algorithm is O(sqrt(n)) because we iterate up to the square root of the given number.

Space Complexity

The space complexity is O(1) as we use only a constant amount of extra space.

class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num <= 1) {
            return false;
        }
        
        int sum = 1;
        
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                sum += i;
                if (i != num / i) {
                    sum += num / i;
                }
            }
        }
        
        return sum == num;
    }
}