Problem Statement
Determine if a given number is a perfect number.
A perfect number is a positive integer that is equal to the sum of its proper divisors (excluding itself).
For example:
- 28 is a perfect number because its proper divisors (1, 2, 4, 7, 14) sum to 28.
- 12 is not a perfect number because its proper divisors (1, 2, 3, 4, 6) sum to 16, not 12.
Example Inputs
Input
Output
true (for 28)false (for 12)
Brute Force Approach
Approach
The brute force method involves finding all divisors of the number (excluding itself) and summing them. If the sum equals the original number, it is a perfect number.
Steps
- Iterate through all numbers from 1 to
n - 1.
- Check if a number is a divisor of
n (i.e., n % i === 0).
- Sum up all such divisors.
- Compare the sum with
n. If they are equal, return true; otherwise, return false.
Time & Space Complexity
- Time Complexity: ( O(n) )
We iterate through all numbers from 1 to ( n-1 ).
- Space Complexity: ( O(1) )
No extra space is used apart from variables.
Code Snippet
Dry Run
Input: 28
- Divisors: 1, 2, 4, 7, 14
- Sum: ( 1 + 2 + 4 + 7 + 14 = 28 )
- ( 28 === 28 ) →
true
Input: 12
- Divisors: 1, 2, 3, 4, 6
- Sum: ( 1 + 2 + 3 + 4 + 6 = 16 )
- ( 16 !== 12 ) →
false
Efficient Approach
Approach
Optimize by iterating only up to ( \sqrt{n} ), as divisors come in pairs. For each divisor ( i ), include both ( i ) and ( n / i ) in the sum.
Steps
- Initialize
sum to 1 (since 1 is a proper divisor of all numbers).
- Iterate from 2 to ( \sqrt{n} ):
- If ( i ) is a divisor, add ( i ) and ( n / i ) to the sum.
- Exclude ( n ) itself from the sum.
- Compare the sum with ( n ). If they are equal, return
true; otherwise, return false.
Time & Space Complexity
- Time Complexity: ( O(\sqrt{n}) )
We only iterate up to ( \sqrt{n} ), reducing the number of checks.
- Space Complexity: ( O(1) )
No extra space is used.
Code Snippet