algoadvance

Leetcode 507. Perfect Number

Problem Statement

A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For example, 28 is a perfect number because its divisors are 1, 2, 4, 7, 14, and 28, and 1 + 2 + 4 + 7 + 14 = 28.

Write a function that checks if a given number is a perfect number.

Clarifying Questions

1. Range of Input: What is the range of the integer that we will be testing for being a perfect number?
   • Assumption: The input is a positive integer and fits within the bounds of a 32-bit signed integer.
2. Return Value: What should be the return type and value?
   • The function should return a boolean value: true if the number is a perfect number and false otherwise.
3. Edge Cases: How to handle the number 1?
   • The number 1 is not a perfect number, so the function should return false for the input 1.

Code

public class PerfectNumber {
    public static 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;
    }

    public static void main(String[] args) {
        int n = 28;
        System.out.println(checkPerfectNumber(n)); // should return true
    }
}

Strategy

1. Initial Check: If num is less than or equal to 1, it cannot be a perfect number, so we return false.
2. Sum of Divisors: Initialize sum to 1 (since 1 is always a divisor for any number larger than 1).
3. Square Root Optimization: To find the divisors more efficiently, iterate from 2 to the square root of num. For each i:
   • If i is a divisor of num, add both i and num/i to the sum (if they are distinct).
4. Comparison: After completing the loop, compare sum with num. If they are equal, return true, otherwise return false.

Time Complexity

• Time Complexity: The time complexity is O(sqrt(n)) because the loop runs until the square root of num.
• Space Complexity: The space complexity is O(1) since we are using a constant amount of extra space.

Edge Cases

• The input number 1 which should return false.
• Smaller perfect numbers like 6 and larger ones like 28.
• Large non-perfect numbers to check the efficiency.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?