Perfect Number
Easy · Math · Math
Problem
A perfect number is a positive integer equal to the sum of its proper divisors: all of its positive divisors except the number itself.
Given an integer num, return true if it is a perfect number and false otherwise.
Examples
Input: num = 496 Output: true
1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 = 496.
Input: num = 12 Output: false
1 + 2 + 3 + 4 + 6 = 16, which is not 12.
Input: num = 1 Output: false
1 has no proper divisors, so the sum is 0.
Constraints
- 1 <= num <= 10^8
Approaches
- Baseline: test every number up to half — time O(n), space O(1)
Follow-up
Only five perfect numbers are at most 10^8 (6, 28, 496, 8128 and 33550336), so a lookup table answers in O(1). Every even perfect number has the form 2^(p-1) · (2^p - 1) with 2^p - 1 prime; whether an odd perfect number exists is still an open question.
Related problems
Start free on Cariara · Coding problems · System design studio
