Perfect Number
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly follows the definition of a perfect number. We iterate through all possible divisors of num from 1 up to num - 1. For each number in this range, we check if it divides num evenly. If it does, we add it to a running sum. Finally, after checking all numbers, we compare this sum with the original number num. If they are equal, num is a perfect number.
Algorithm
- First, handle the edge case where
num <= 1. Since perfect numbers are positive integers greater than 1, returnfalse. - Initialize a variable
sumto 0 to store the sum of the divisors. - Iterate with a loop variable
ifrom 1 up tonum - 1. - Inside the loop, use the modulo operator (
%) to check ifiis a divisor ofnum(i.e.,num % i == 0). - If
iis a divisor, add it tosum. - After the loop completes, compare
sumwithnum. If they are equal, it meansnumis a perfect number, so returntrue. Otherwise, returnfalse.
Walkthrough
class Solution { public boolean 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; }}Complexity
Time
O(n) - The loop runs from 1 to `num - 1`, so the number of operations is directly proportional to `num`. For the given constraint of `num <= 10^8`, this approach will be too slow and likely result in a 'Time Limit Exceeded' error.
Space
O(1) - We only use a few variables (`sum`, `i`) to store intermediate values, regardless of the size of `num`. The space required is constant.
Trade-offs
Pros
Simple to understand and implement.
Directly translates the mathematical definition into code.
Cons
Highly inefficient for large values of
num.Will not pass the time limits for the given constraints.
This approach improves upon the brute-force method by recognizing that divisors come in pairs. If i is a divisor of num, then num / i is also a divisor. We only need to iterate up to the square root of num. For each divisor i we find, we add both i and its corresponding pair num / i to the sum. This significantly reduces the number of iterations required.
Algorithm
- Handle the edge case: if
num <= 1, it cannot be a perfect number, so returnfalse. - Initialize a variable
sumto 1. We pre-add 1 as it's a divisor for allnum > 1. This allows us to start the loop from 2. - Iterate with a loop variable
ifrom 2 up tosqrt(num)(i.e.,i * i <= num). - Inside the loop, check if
iis a divisor ofnum(num % i == 0). - If it is, add
ito thesum. We also need to add its pair,num / i. - A special case arises if
numis a perfect square. In this case,iandnum / iare the same. To avoid adding the square root twice, we only addnum / iifi * i != num. - After the loop, compare the final
sumwithnum.
Walkthrough
class Solution { public boolean checkPerfectNumber(int num) { if (num <= 1) { return false; } int sum = 1; for (int i = 2; i * i <= num; i++) { if (num % i == 0) { sum += i; if (i * i != num) { sum += num / i; } } } return sum == num; }}Complexity
Time
O(sqrt(n)) - The loop runs from 2 up to the square root of `num`. This is a significant improvement over the O(n) approach and is efficient enough to pass the time limits for `num <= 10^8`.
Space
O(1) - Similar to the brute-force approach, the space used is constant as it does not depend on the input size.
Trade-offs
Pros
Much more efficient than the brute-force approach.
Passes the time constraints of the problem.
Cons
Slightly more complex logic due to handling divisor pairs and the perfect square case.
This is a mathematical approach that leverages the Euclid-Euler theorem. The theorem provides a formula for all known (even) perfect numbers: 2^(p-1) * (2^p - 1), where p is a prime and 2^p - 1 is a Mersenne prime. Given the constraint num <= 10^8, we can pre-calculate all perfect numbers that fall within this range. There are only five such numbers: 6, 28, 496, 8128, and 33550336. The problem then reduces to simply checking if the input num is one of these five values.
Algorithm
- Identify all perfect numbers up to the constraint
10^8using the Euclid-Euler theorem.- For p=2:
2^1 * (2^2 - 1) = 6 - For p=3:
2^2 * (2^3 - 1) = 28 - For p=5:
2^4 * (2^5 - 1) = 496 - For p=7:
2^6 * (2^7 - 1) = 8128 - For p=13:
2^12 * (2^13 - 1) = 33550336
- For p=2:
- Since it is an open mathematical problem whether any odd perfect numbers exist, we can safely assume for this problem that we only need to consider these five even perfect numbers.
- Implement a check, for instance using a
switchstatement, to see if the inputnummatches any of these five pre-calculated values. - Return
trueif a match is found, andfalseotherwise.
Walkthrough
class Solution { public boolean checkPerfectNumber(int num) { // The known perfect numbers within the constraint 1 <= num <= 10^8 // are 6, 28, 496, 8128, and 33550336. switch (num) { case 6: case 28: case 496: case 8128: case 33550336: return true; default: return false; } }}Complexity
Time
O(1) - The solution involves a fixed number of comparisons, regardless of the input `num`. This is the most efficient time complexity possible.
Space
O(1) - No extra space is used that scales with the input. The storage for the hardcoded numbers is constant.
Trade-offs
Pros
Extremely fast and efficient.
Simple and clean implementation.
Cons
Relies on pre-existing mathematical knowledge (Euclid-Euler theorem).
The solution is specific to the given constraints; if the constraints were much larger, this approach would require pre-calculating more perfect numbers.
Solutions
Solution
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 != num / i) { s += num / i; } } } return s == num; }}class Solution: def checkPerfectNumber(self, num: int) -> bool: if num == 1: return False s, i = 1, 2 while i * i <= num: if num % i == 0: s += i if i != num // i: s += num // i i += 1 return s == numclass Solution {public: bool 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 != num / i) s += num / i; } } return s == num; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.