Skip to main content
Talentd

Perfect Number - Solution & Explanation

EasyMath14 min readAsked at: Amazon, Microsoft, Meta +5
Practice this problem

Problem Statement

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.

The function first checks if num is less than or equal to 1, returning false if so, as there's no perfect number <= 1. Then it initializes sum with 1 since 1 is a divisor of every number except itself. We iterate through possible divisors up to the square root of num. If i is a divisor, we add it and its pair num/i to sum, avoiding double counting. Finally, we check if sum equals num.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(sqrt(n))
Space Complexity: O(1)

Try this approach in the editor ā†’

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.

The C solution performs a simple loop through possible divisors from 1 to num - 1, summing any divisors found and checking if this total matches num.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor ā†’

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Optimized Divisor Sum with Square Root Iteration

Time Complexity: O(sqrt(n))
Space Complexity: O(1)

Naive Divisor Sum

Time Complexity: O(n)
Space Complexity: O(1)

Enumerationā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Divisor SumO(n)O(1)Simple implementation or when constraints are very small
Square Root Divisor IterationO(sqrt(n))O(1)Optimal approach for interviews and large inputs

Video Solution

LeetCode 507 : Perfect Number || EASY || JAVA || Detailed Solution ā€¢ CodeGPT ā€¢ 1,625 views views

Watch 9 more video solutions ā†’

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.

Ready to solve this problem?

Practice Perfect Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Self Dividing Numbers