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 <= 108Problem Overview: A perfect number is a positive integer equal to the sum of its proper divisors (all divisors excluding the number itself). Given an integer num, determine whether the sum of its divisors equals the number.
This problem sits in the math and number theory category. The task is essentially divisor enumeration and efficient summation.
Approach 1: Naive Divisor Sum (O(n) time, O(1) space)
The straightforward solution iterates through every integer from 1 to num - 1 and checks whether it divides num. If num % i == 0, add i to a running sum. After the loop finishes, compare the sum with num. If they match, the number is perfect.
This method directly follows the definition of a perfect number. The drawback is the linear scan up to n, which becomes inefficient for large inputs. It works fine for small constraints and demonstrates understanding of divisor properties.
Approach 2: Optimized Divisor Sum with Square Root Iteration (O(sqrt(n)) time, O(1) space)
Divisors appear in pairs. If i divides num, then num / i is also a divisor. Instead of checking every number up to n, iterate only from 2 to sqrt(num). Whenever num % i == 0, add both i and num / i to the sum.
Initialize the sum with 1 because 1 is always a proper divisor (except for edge cases like num = 1). While iterating, handle perfect squares carefully so the same divisor is not counted twice when i * i == num. This reduces the search space dramatically from n checks to about sqrt(n).
The optimization comes from recognizing the mathematical symmetry of divisors. Each factor below the square root corresponds to a partner above it. This approach is standard in divisor-based problems and appears frequently in math interview questions.
Recommended for interviews: The square root divisor iteration is the expected solution. It demonstrates awareness of divisor pairing and reduces the complexity from O(n) to O(sqrt(n)). Starting with the naive scan is acceptable to show the basic idea, but the optimized version signals stronger algorithmic thinking.
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.
The function first checks if num is less than or equal to 1, returning false if so, as there's no perfect number <= 1. Then it initializes sum with 1 since 1 is a divisor of every number except itself. We iterate through possible divisors up to the square root of num. If i is a divisor, we add it and its pair num/i to sum, avoiding double counting. Finally, we check if sum equals num.
Time Complexity: O(sqrt(n))
Space Complexity: O(1)
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.
The C solution performs a simple loop through possible divisors from 1 to num - 1, summing any divisors found and checking if this total matches num.
Time Complexity: O(n)
Space Complexity: O(1)
First, we check if num is 1. If it is, then num is not a perfect number, and we return false.
Next, we enumerate all positive divisors of num starting from 2. If num is divisible by a positive divisor i, we add i to the sum s. If the quotient of num divided by i is not equal to i, we also add the quotient to the sum s.
Finally, we check if s is equal to num.
The time complexity is O(\sqrt{n}), where n is the value of num. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Optimized Divisor Sum with Square Root Iteration | Time Complexity: O(sqrt(n)) |
| Naive Divisor Sum | Time Complexity: O(n) |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Divisor Sum | O(n) | O(1) | Simple implementation or when constraints are very small |
| Square Root Divisor Iteration | O(sqrt(n)) | O(1) | Optimal approach for interviews and large inputs |
507. Perfect Number (LeetCode) • hakunamatasq • 2,093 views views
Watch 9 more video solutions →Practice Perfect Number with our built-in code editor and test cases.
Practice on FleetCode