Perfect Number — Solution in Python, Java & C++
Perfect Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and TCS.
Perfect Number is an easy coding problem on math, asked in Amazon, TCS, Infosys and Accenture interviews.
- Difficulty: Easy
- Topics: Math
- Asked at: Amazon, TCS, Infosys, Accenture
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A perfect number is a positive integer that equals the sum of its positive divisors, excluding the number itself. A divisor of an integer x is an integer that divides x exactly.
Given an integer num, return true if it is a perfect number.
Example 1
Input: num = 28
Output: true
Explanation: 28 = 1 + 2 + 4 + 7 + 14.
Example 2
Input: num = 7
Output: false
Explanation: Its only proper divisor is 1.
Example 3
Input: num = 6
Output: true
Explanation: 6 = 1 + 2 + 3.
Constraints
1 <= num <= 1000000
Hints for Perfect Number
Hint 1
Only test divisors up to √num — each small divisor
dpairs withnum / d.Hint 2
Seed the sum with 1 and start the loop at 2, so
numitself is never added.Hint 3
Watch the perfect square case: when
d * d == num, adddonly once.
How to solve Perfect Number
Divisors come in pairs (d, num / d), so testing d only up to √num finds them all. Seed the sum with 1 so num itself is excluded.
Approach
- Return
falsefornum <= 1. - Start
total = 1andd = 2. - While
d * d <= num: ifddividesnum, adddand — when different —num / d. - Return
total == num.
Why it works
If d divides num then so does num / d, and one of the two is at most √num; enumerating the small member of each pair therefore enumerates every proper divisor exactly once, with the square root handled by the other != d check.
Complexity
- Time —
O(√num) - Space —
O(1)
Pitfalls
- Starting the loop at 1 counts
numitself as the partner of 1. - For a perfect square,
dandnum / dcoincide and must be added once.
Reference solution
Python
def checkPerfectNumber(num: int) -> bool:
if num <= 1:
return False
total = 1
d = 2
while d * d <= num:
if num % d == 0:
total += d
other = num // d
if other != d:
total += other
d += 1
return total == numJava
public static boolean checkPerfectNumber(int num) {
if (num <= 1) return false;
long total = 1;
for (int d = 2; (long) d * d <= num; d++) {
if (num % d == 0) {
total += d;
int other = num / d;
if (other != d) total += other;
}
}
return total == num;
}C++
bool checkPerfectNumber(int num) {
if (num <= 1) return false;
long long total = 1;
for (int d = 2; (long long) d * d <= num; d++) {
if (num % d == 0) {
total += d;
int other = num / d;
if (other != d) total += other;
}
}
return total == (long long) num;
}JavaScript
var checkPerfectNumber = function(num) {
if (num <= 1) return false;
let total = 1;
for (let d = 2; d * d <= num; d++) {
if (num % d === 0) {
total += d;
const other = num / d;
if (other !== d) total += other;
}
}
return total === num;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.