Sponsored
Sponsored
The main idea is that divisors come in pairs, and for each pair (d, n/d), if d is less than the square root of n, then d and n/d are both divisors of n. This approach allows us to only iterate up to the square root of n, making it more efficient.
Time Complexity: O(sqrt(n))
Space Complexity: O(1)
1import math
2
3def checkPerfectNumber(num: int) -> bool:
4 if num <= 1:
5 return False
6 sum = 1
7 sqrt_num = int(math.sqrt(num))
8 for i in range(2, sqrt_num + 1):
9 if num % i == 0:
10 sum += i
11 if i != num // i:
12 sum += num // i
13 return sum == numThe Python solution employs the math library to utilize the square root function. We check numbers up to the square root of the input, summing divisors as described and returning whether sum matches the original number.
This approach calculates the sum of all divisors excluding the number itself by checking each integer from 1 to n-1 to determine if it's a divisor, then sums these and checks if the sum equals n. This method is simple but inefficient for large numbers.
Time Complexity: O(n)
Space Complexity: O(1)
1class Solution {
2public:
bool checkPerfectNumber(int num) {
if (num <= 1) return false;
int sum = 0;
for (int i = 1; i < num; ++i) {
if (num % i == 0) {
sum += i;
}
}
return sum == num;
}
};The C++ version executes the naive approach, iterating through all integers from 1 to slightly less than the input number and summing up any divisors it encounters.