LeetCode 507: Perfect Number Solution

Problem Explanation

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:

Initialize sum as 1 (since 1 is always a divisor).
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.
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.

Solution Code

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

Frequently Asked Questions

How to solve LeetCode 507 (Perfect Number)?

This page provides optimized solutions for LeetCode problem 507 (Perfect Number) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 507 (Perfect Number)?

The time complexity for LeetCode 507 (Perfect Number) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 507 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 507 in Java, C++, or Python.

507. Perfect Number