Perfect Number solution and explanation
Google
9 more videos on this problem
LeetCode 507 : Perfect Number || EASY || JAVA || Detailed SolutionCodeGPT · 9:40 · 1K views
Leetcode 507. Perfect Number Python SolutionTechZoo · 5:01 · 1K views
Leetcode 507.Perfect NumberFriendly Neighborhood Coder · 7:23 · 1K views
LeetCode 507. Perfect Number Solution Explained - JavaAlgorithms and Data Structures Course · 4:55 · 791 views
How to Solve "507 Perfect Number" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 4:59 · 616 views
LeetCode 507 | Perfect Number | Math | JavaSleepy Cracker · 4:31 · 612 views
Leetcode 507. Perfect Number ➗ Sum Divisors, Perfect Delivers! 👌🏼💯LEETCODE SIMPLIFIED · 4:52 · 339 views
LeetCode 507 - Perfect Number | Easy C++ Solution 🚀Dhruva Tajapara · 4:57 · 246 views
LeetCode 507 | Perfect Number | Easy LeetCode Problem Explanation in JavaCODE WITH PUSHPRAJ · 8:35 · 224 views
#LeetCode 507 || Perfect Number || #leetcode || #perfectnumberJet To Mastery · 8:37 · 207 views
The problem
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
Approach overview
Problem Overview: A perfect number is a positive integer equal to the sum of its proper divisors (all divisors excluding the number itself). Given an integer num, determine whether the sum of its divisors equals the number.
This problem sits in the math and number theory category. The task is essentially divisor enumeration and efficient summation.
Approach 1: Naive Divisor Sum (O(n) time, O(1) space)
The straightforward solution iterates through every integer from 1 to num - 1 and checks whether it divides num. If num % i == 0, add i to a running sum. After the loop finishes, compare the sum with num. If they match, the number is perfect.
This method directly follows the definition of a perfect number. The drawback is the linear scan up to n, which becomes inefficient for large inputs. It works fine for small constraints and demonstrates understanding of divisor properties.
Approach 2: Optimized Divisor Sum with Square Root Iteration (O(sqrt(n)) time, O(1) space)
Divisors appear in pairs. If i divides num, then num / i is also a divisor. Instead of checking every number up to n, iterate only from 2 to sqrt(num). Whenever num % i == 0, add both i and num / i to the sum.
Initialize the sum with 1 because 1 is always a proper divisor (except for edge cases like num = 1). While iterating, handle perfect squares carefully so the same divisor is not counted twice when i * i == num. This reduces the search space dramatically from n checks to about sqrt(n).
The optimization comes from recognizing the mathematical symmetry of divisors. Each factor below the square root corresponds to a partner above it. This approach is standard in divisor-based problems and appears frequently in math interview questions.
Recommended for interviews: The square root divisor iteration is the expected solution. It demonstrates awareness of divisor pairing and reduces the complexity from O(n) to O(sqrt(n)). Starting with the naive scan is acceptable to show the basic idea, but the optimized version signals stronger algorithmic thinking.
Approach 1: Optimized Divisor Sum with Square Root Iteration
The main idea is that divisors come in pairs, and for each pair (d, n/d), if d is less than the square root of n, then d and n/d are both divisors of n. This approach allows us to only iterate up to the square root of n, making it more efficient.
import math
def checkPerfectNumber(num: int) -> bool:
if num <= 1:
return False
sum = 1
sqrt_num = int(math.sqrt(num))
for i in range(2, sqrt_num + 1):
if num % i == 0:
sum += i
if i != num // i:
sum += num // i
return sum == numpublic class Solution {
public boolean checkPerfectNumber(int num) {
if (num <= 1) return false;
int sum = 1;
int sqrtNum = (int) Math.sqrt(num);
for (int i = 2; i <= sqrtNum; i++) {
if (num % i == 0) {
sum += i;
if (i != num / i) sum += num / i;
}
}
return sum == num;
}
}#include <cmath>
class Solution {
public:
bool checkPerfectNumber(int num) {
if (num <= 1) return false;
int sum = 1;
int sqrtNum = static_cast<int>(sqrt(num));
for (int i = 2; i <= sqrtNum; i++) {
if (num % i == 0) {
sum += i;
if (i != num / i) sum += num / i;
}
}
return sum == num;
}
};function checkPerfectNumber(num) {
if (num <= 1) return false;
let sum = 1;
const sqrtNum = Math.floor(Math.sqrt(num));
for (let i = 2; i <= sqrtNum; i++) {
if (num % i === 0) {
sum += i;
if (i !== num / i) sum += num / i;
}
}
return sum === num;
}#include <stdbool.h>
#include <math.h>
bool isPerfectNumber(int num) {
if (num <= 1) return false;
int sum = 1;
int sqrtNum = (int)sqrt(num);
for (int i = 2; i <= sqrtNum; i++) {
if (num % i == 0) {
sum += i;
if (i != num / i) sum += num / i;
}
}
return sum == num;
}using System;
public class Solution {
public bool CheckPerfectNumber(int num) {
if (num <= 1) return false;
int sum = 1;
int sqrtNum = (int)Math.Sqrt(num);
for (int i = 2; i <= sqrtNum; i++) {
if (num % i == 0) {
sum += i;
if (i != num / i) sum += num / i;
}
}
return sum == num;
}
}The Python solution employs the math library to utilize the square root function. We check numbers up to the square root of the input, summing divisors as described and returning whether sum matches the original number.
Time Complexity: O(sqrt(n))
Space Complexity: O(1)
Approach 2: Naive Divisor Sum
This approach calculates the sum of all divisors excluding the number itself by checking each integer from 1 to n-1 to determine if it's a divisor, then sums these and checks if the sum equals n. This method is simple but inefficient for large numbers.
def checkPerfectNumber(num: int) -> bool:
if num <= 1:
return False
sum = 0
for i in range(1, num):
if num % i == 0:
sum += i
return sum == numpublic class Solution {
public boolean checkPerfectNumber(int num) {
if (num <= 1) return false;
int sum = 0;
for (int i = 1; i < num; ++i) {
if (num % i == 0) {
sum += i;
}
}
return sum == num;
}
}class Solution {
public:
bool checkPerfectNumber(int num) {
if (num <= 1) return false;
int sum = 0;
for (int i = 1; i < num; ++i) {
if (num % i == 0) {
sum += i;
}
}
return sum == num;
}
};function checkPerfectNumber(num) {
if (num <= 1) return false;
let sum = 0;
for (let i = 1; i < num; i++) {
if (num % i === 0) {
sum += i;
}
}
return sum === num;
}#include <stdbool.h>
bool isPerfectNumber(int num) {
if (num <= 1) return false;
int sum = 0;
for (int i = 1; i < num; ++i) {
if (num % i == 0) {
sum += i;
}
}
return sum == num;
}public class Solution {
public bool CheckPerfectNumber(int num) {
if (num <= 1) return false;
int sum = 0;
for (int i = 1; i < num; ++i) {
if (num % i == 0) {
sum += i;
}
}
return sum == num;
}
}In Python, the simplicity of this method is evident as it loops through potential divisors, calculating their total and making a comparison against the input value.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Enumeration
First, we check if num is 1. If it is, then num is not a perfect number, and we return false.
Next, we enumerate all positive divisors of num starting from 2. If num is divisible by a positive divisor i, we add i to the sum s. If the quotient of num divided by i is not equal to i, we also add the quotient to the sum s.
Finally, we check if s is equal to num.
The time complexity is O(\sqrt{n}), where n is the value of num. The space complexity is O(1).
function checkPerfectNumber(num: number): boolean {
if (num <= 1) {
return false;
}
let s = 1;
for (let i = 2; i <= num / i; ++i) {
if (num % i === 0) {
s += i;
if (i * i !== num) {
s += num / i;
}
}
}
return s === num;
}func checkPerfectNumber(num int) bool {
if num == 1 {
return false
}
s := 1
for i := 2; i <= num/i; i++ {
if num%i == 0 {
s += i
if j := num / i; i != j {
s += j
}
}
}
return s == num
}Complexity comparison
| Approach | Complexity |
|---|---|
| Optimized Divisor Sum with Square Root Iteration | Time Complexity: O(sqrt(n)) |
| Naive Divisor Sum | Time Complexity: O(n) |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Divisor Sum | O(n) | O(1) | Simple implementation or when constraints are very small |
| Square Root Divisor Iteration | O(sqrt(n)) | O(1) | Optimal approach for interviews and large inputs |
Frequently asked questions
Is Perfect Number easy or hard?
Perfect Number is classified as an Easy problem. The core idea is simple divisor summation, but recognizing the sqrt optimization improves efficiency and demonstrates stronger mathematical reasoning.
Perfect Number Python/Java solution
In Python or Java, implement a loop from 2 to sqrt(n) and check divisibility using the modulo operator. When a divisor is found, add both the divisor and its pair (n/i) to the sum. Initialize the sum with 1 and compare the final sum with n.
How to solve Perfect Number in O(n)?
Iterate from 1 to n-1 and check if each number divides n using n % i == 0. Add all such divisors to a running sum. After the loop, compare the sum with the original number. If they are equal, the number is perfect.
What is the best approach for Perfect Number?
The best approach uses square root divisor iteration. Instead of checking every number up to n, iterate only up to sqrt(n) and add both divisors in each pair (i and n/i). This reduces the time complexity to O(sqrt(n)) while using constant space.
Is Perfect Number asked at Google/Amazon/Meta?
Perfect Number appears as a basic math or number theory screening question and is more common in early interview rounds. Companies like Amazon and smaller tech firms sometimes use it to test divisor logic and basic optimization using sqrt iteration.
What data structure is used in Perfect Number?
No special data structure is required. The problem relies on mathematical divisor checks and simple integer iteration. Only a few variables are used to track the running sum and loop counters, so the space complexity remains O(1).
What is the time complexity of Perfect Number?
The optimal solution runs in O(sqrt(n)) time because it only checks divisors up to the square root of the number. The naive approach checks every integer from 1 to n−1, which results in O(n) time complexity. Both approaches use O(1) space.