507. Perfect Number
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 36.3%
Problem Breakdown
The problem asks us to determine if a given integer n is a perfect number. A perfect number is defined as a positive integer that is equal to the sum of its positive divisors, excluding the number itself. The input is a single integer n, and the output should be a boolean value: true if n is a perfect number, otherwise false.
Inputs:
- A single integer
nwhere1 <= n <= 10^8.
Outputs:
- A boolean value (
trueorfalse).
Implicit Constraints and Edge Cases:
- The smallest possible input is
1, which has no divisors other than itself, so it should returnfalse. - Numbers like
2,3, etc., that are not perfect numbers should returnfalse.
Intuition
The brute-force approach would involve iterating through all integers from 1 to n-1 to check if they are divisors of n. If the sum of these divisors equals n, then n is a perfect number. However, this approach has a time complexity of O(n), which is inefficient given the constraint n <= 10^8.
A more efficient approach leverages the fact that divisors come in pairs. For example, if d is a divisor of n, then n/d is also a divisor. This insight allows us to reduce the number of iterations significantly by only checking up to the square root of n. If d is a divisor and d != n/d, both d and n/d should be added to the sum of divisors.
Approach
- Edge Case Handling: If
nis less than or equal to 1, returnfalseimmediately since no number less than or equal to 1 can be a perfect number. - Initialize Variables: Start with a variable
sum_of_divisorsinitialized to 1 (since 1 is a divisor of every positive integer). - Iterate Over Possible Divisors: Loop from
i = 2to the square root ofn. For eachi, check if it dividesnevenly.- If
iis a divisor, add bothiandn/itosum_of_divisors. - To avoid adding the square root twice when
i * i == n, ensure thati != n/i.
- If
- Check for Perfect Number: After the loop, compare
sum_of_divisorswithn. If they are equal, returntrue; otherwise, returnfalse.
Complexity Analysis
- Time Complexity: O(√n) because we only iterate up to the square root of
n. - Space Complexity: O(1) since we use a constant amount of extra space.
Solution
def checkPerfectNumber(num: int) -> bool:
if num <= 1:
return False
sum_of_divisors = 1
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
sum_of_divisors += i
if i != num // i:
sum_of_divisors += num // i
return sum_of_divisors == num
Edge Cases Handled
- Edge Case 1:
num = 1- Returnsfalsebecause 1 has no divisors other than itself. - Edge Case 2:
num = 2- Returnsfalsebecause the only divisor is 1, and 1 + 0 != 2. - Perfect Numbers: The function correctly identifies known perfect numbers like 6, 28, 496, and 8128 by returning
true. - Non-perfect Numbers: Any number that does not meet the criteria for a perfect number returns
false.