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 instance, 28 is a perfect number because its divisors are 1, 2, 4, 7, and 14, and 1 + 2 + 4 + 7 + 14 = 28.

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

Clarifying Questions

1. Input Constraints:
   • What is the range of the input integer? (e.g., 1 to (10^8))
   • Can the input be zero or a negative number?
2. Output:
   • Should the function return a boolean value (true or false) indicating whether the given number is a perfect number?

Let’s assume:

• The input integer is in the range from 1 to (10^8).
• The input integer is always positive.

Code

#include <iostream>
#include <cmath>

class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num <= 1) return false;  // No perfect number less than or equal to 1
        
        int sum = 1;  // Start with 1 because 1 is a divisor of all numbers
        int sqrtNum = std::sqrt(num);
        
        for (int i = 2; i <= sqrtNum; i++) {
            if (num % i == 0) {
                sum += i;
                if (i != num / i) {
                    sum += num / i;
                }
            }
        }
        
        return sum == num;
    }
};

int main() {
    Solution solution;
    int num = 28;
    std::cout << "Is " << num << " a perfect number? " << (solution.checkPerfectNumber(num) ? "Yes" : "No") << std::endl;
    return 0;
}

Strategy

1. Initial Check: If the number is less than or equal to 1, return false as there are no perfect numbers less than or equal to 1.
2. Summing Divisors:
   • Start with a sum of 1 because 1 is a divisor of all numbers.
   • Iterate over possible divisors from 2 up to the square root of the number.
   • If i is a divisor, add i and also add the corresponding divisor num / i (if it’s different from i).
   • The use of the square root reduces the number of iterations needed.
3. Final Check: If the sum of the divisors equals the original number, then it is a perfect number. Otherwise, it is not.

Time Complexity

• Time Complexity: (O(\sqrt{n}))
  • This is because the loop runs from 2 to the square root of num.
• Space Complexity: (O(1))
  • We use a constant amount of extra space regardless of the input size.

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?