Practice › Basics
Perfect Number
Easy · Basics · Asked at TCS, Infosys, Wipro, Accenture, Cognizant
A perfect number equals the sum of its proper divisors (all divisors except itself). For example 28 = 1 + 2 + 4 + 7 + 14. Print YES if n is perfect, otherwise NO.
Input
A single integer n.
Output
YES or NO.
Constraints
- 1 ≤ n ≤ 10^12
Divisors come in pairs (d, n/d), so you only need to loop up to √n.
Example 1
Input
28
Output
YES
Example 2
Input
12
Output
NO
Hints
- You need the sum of all divisors smaller than n.
- Loop d only up to √n and add both d and n/d (once if they are equal).
Approach
Start the sum at 1 (every n > 1 has divisor 1), then for every d from 2 while d·d ≤ n: if d divides n, add d and its partner n/d (only once when d·d = n). Compare the sum with n. 1 is not perfect (its proper-divisor sum is 0). √(10^12) = 10^6 iterations.
Complexity: O(√n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
if (n == 1) {
cout << "NO\n";
return 0;
}
long long sum = 1;
for (long long d = 2; d * d <= n; d++) {
if (n % d == 0) {
sum += d;
if (d * d != n) sum += n / d;
}
}
cout << (sum == n ? "YES" : "NO") << "\n";
return 0;
}Python solution
n = int(input())
total = 1 if n > 1 else 0
d = 2
while d * d <= n:
if n % d == 0:
total += d
if d * d != n:
total += n // d
d += 1
print("YES" if n > 1 and total == n else "NO")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
long n = new Scanner(System.in).nextLong();
if (n == 1) {
System.out.println("NO");
return;
}
long sum = 1;
for (long d = 2; d * d <= n; d++) {
if (n % d == 0) {
sum += d;
if (d * d != n) sum += n / d;
}
}
System.out.println(sum == n ? "YES" : "NO");
}
}