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
My Solution
We can solve this problem by iterating from 2 to the square root of num and if num is divisible by that number, we add that number along with num / i to our running sum. If num is 1, this is a special case where we return false. If in the end, sum is equal to num, we return true. Otherwise, we return false.
Time complexity is O(sqrt(num)) because we iterate over O(sqrt(num)) numbers. Space complexity is O(1) since we only require constant extra space.
class Solution {
public boolean checkPerfectNumber(int num) {
if (num == 1) {
return false;
}
int sum = 1;
int sqrt = (int) Math.sqrt(num);
for (int i = 2; i <= sqrt; i++) {
if (num % i == 0) {
sum += (i + num / i);
}
}
return (sum == num);
}
}