254. Perfect Total
An old arithmetic club calls a positive integer balanced when the sum of all of its divisors that are smaller than itself equals the number. For instance the proper divisors of 28 are 1, 2, 4, 7 and 14, and they add up to exactly 28. The club wants a quick checker that works even for values close to two billion.
Given the integer n, return true if the sum of its positive divisors excluding n itself equals n, and false otherwise. Numbers below 2 are never balanced. Looping over every number below n is too slow; use the fact that divisors come in pairs and aim for roughly square-root time with constant extra space.
Example 1
- Input:
- n = 8128
- Output:
- true
- Explanation:
The proper divisors of 8128 sum to exactly 8128, so it is balanced.
Example 2
- Input:
- n = 8129
- Output:
- false
- Explanation:
8129 = 11 * 739 has proper divisors summing to 751, so the answer is false.
Example 3
- Input:
- n = 1
- Output:
- false
- Explanation:
1 has no proper divisors, so the sum is 0 and the answer is false.
Constraints
1 ≤ n ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(sqrt(n))
- Space
- O(1)