507. Perfect Number

📝 Problem Details

• Title: 507. Perfect Number
• Link: https://leetcode.com/problems/perfect-number/
• Difficulty: Easy
• Tags/Categories: Math Modulo-Operator

💭What Were My Initial Thoughts?

~

🤔What Did I Struggle With?

- how the modulo operator is used in this problem
	- used to determine if a number i is a divisor of another number n
	- n % i == 0 means that i can be divided by n evenly so it is a divisor of n

💡 Explanation of Solution

- ensure input `num` is positive because perfect numbers are positive integers
- proper divisors of n are all numbers less than n that divide n evenly
- since divisors come in pairs 
	- (e.g., for n=28, divisors include 1-28, 2,14), you only need to iterate up to sqrt(n)
- as you find divisors, add them to a running total
- remember to exclude n itself
- if the sum of the proper divisors == n then its a perfect number

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    bool checkPerfectNumber(int n) {
        if(n <= 1) return false;
        
        int divisorSum = 1; // start with 1 because it is always a divisor
 
        for(int i=2; i <= sqrt(n); i++) {
            if(n % i == 0) {
                divisorSum += i;
                if(i != n/i) {
                    divisorSum += n / i; // add the complementary divisor
                }
            }
        }
        return divisorSum == n;
    }
};