Scale Engineer

Perfect Number

Easy
#0494Time: O(n) - The loop runs from 1 to `num - 1`, so the number of operations is directly proportional to `num`. For the given constraint of `num <= 10^8`, this approach will be too slow and likely result in a 'Time Limit Exceeded' error.Space: O(1) - We only use a few variables (`sum`, `i`) to store intermediate values, regardless of the size of `num`. The space required is constant.2 companies
Patterns
Math
Companies
AccentureGrammarly

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly follows the definition of a perfect number. We iterate through all possible divisors of num from 1 up to num - 1. For each number in this range, we check if it divides num evenly. If it does, we add it to a running sum. Finally, after checking all numbers, we compare this sum with the original number num. If they are equal, num is a perfect number.

Algorithm

  • First, handle the edge case where num <= 1. Since perfect numbers are positive integers greater than 1, return false.
  • Initialize a variable sum to 0 to store the sum of the divisors.
  • Iterate with a loop variable i from 1 up to num - 1.
  • Inside the loop, use the modulo operator (%) to check if i is a divisor of num (i.e., num % i == 0).
  • If i is a divisor, add it to sum.
  • After the loop completes, compare sum with num. If they are equal, it means num is a perfect number, so return true. Otherwise, return false.

Walkthrough

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;    }}

Complexity

Time

O(n) - The loop runs from 1 to `num - 1`, so the number of operations is directly proportional to `num`. For the given constraint of `num <= 10^8`, this approach will be too slow and likely result in a 'Time Limit Exceeded' error.

Space

O(1) - We only use a few variables (`sum`, `i`) to store intermediate values, regardless of the size of `num`. The space required is constant.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly translates the mathematical definition into code.

Cons

  • Highly inefficient for large values of num.

  • Will not pass the time limits for the given constraints.

Solutions

class Solution {public  boolean checkPerfectNumber(int num) {    if (num == 1) {      return false;    }    int s = 1;    for (int i = 2; i * i <= num; ++i) {      if (num % i == 0) {        s += i;        if (i != num / i) {          s += num / i;        }      }    }    return s == num;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem