LeetCode 507 : Perfect Number || EASY || JAVA || Detailed Solution
Perfect Number - Video Solution
Watch 10 video solutions for Perfect Number, a easy level problem involving Math. This walkthrough by CodeGPT has 1,625 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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
Approach Overview
Problem 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.
Complexity Analysis
| 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 |