{x}
blog image

Perfect Number

A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. A divisor of an integer x is an integer that can divide x evenly.

Given an integer n, return true if n is a perfect number, otherwise return false.

 

Example 1:

Input: num = 28
Output: true
Explanation: 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.

Example 2:

Input: num = 7
Output: false

 

Constraints:

  • 1 <= num <= 108

Solution Explanation: Perfect Number

The problem asks to determine if a given positive integer num is a perfect number. A perfect number is a positive integer that is equal to the sum of its proper divisors (excluding itself).

Approach: Efficient Enumeration

The most efficient approach involves iterating only up to the square root of num. This is because divisors come in pairs. If i is a divisor, then num/i is also a divisor. We only need to explicitly find divisors up to the square root; the others are implicitly found.

Algorithm:

  1. Handle Base Case: If num is 1, it's not a perfect number, so return false.

  2. Initialize Sum: Initialize a variable s to 1 (since 1 is always a divisor).

  3. Iterate up to the Square Root: Iterate through numbers i from 2 up to the square root of num.

  4. Check for Divisibility: If num is divisible by i (i.e., num % i == 0), then:

    • Add i to the sum s.
    • If i is not equal to num/i (this avoids adding the same divisor twice when i is the square root of num), add num/i to s.

  5. Compare Sum to Number: After the loop, check if the sum s is equal to num. If they are equal, num is a perfect number, and we return true; otherwise, return false.

Code Implementations

The following code implements the algorithm in several languages:

Python3

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num == 1:
            return False
        s = 1
        i = 2
        while i * i <= num:
            if num % i == 0:
                s += i
                if i * i != num:
                    s += num // i
            i += 1
        return s == num

Java

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

C++

class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num == 1) return false;
        int s = 1;
        for (long long i = 2; i * i <= num; ++i) { //Note: use long long to prevent overflow
            if (num % i == 0) {
                s += i;
                if (i * i != num) s += num / i;
            }
        }
        return s == num;
    }
};

Go

func checkPerfectNumber(num int) bool {
	if num <= 1 {
		return false
	}
	sum := 1
	for i := 2; i*i <= num; i++ {
		if num%i == 0 {
			sum += i
			if i*i != num {
				sum += num / i
			}
		}
	}
	return sum == num
}

TypeScript

function checkPerfectNumber(num: number): boolean {
    if (num <= 1) return false;
    let sum = 1;
    for (let i = 2; i * i <= num; i++) {
        if (num % i === 0) {
            sum += i;
            if (i * i !== num) {
                sum += num / i;
            }
        }
    }
    return sum === num;
}

Time and Space Complexity Analysis

  • Time Complexity: O(√n). The loop iterates up to the square root of n.

  • Space Complexity: O(1). The algorithm uses a constant amount of extra space.

This optimized approach significantly improves efficiency compared to a naive solution that iterates through all numbers up to n.