Skip to main content

507. Perfect Number

easy

Decide whether a positive integer equals the sum of its proper divisors. A classic number-theory warm-up — trial division up to sqrt(n) gets you O(sqrt(n)) easily.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Constraints

  • 1 <= num <= 10^8

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Iterating divisors d from 1 to n-1 is O(n). For n up to 10^8 that's too slow.

Hint 2

Divisors come in pairs (d, n/d). One of each pair is <= sqrt(n). So iterate d from 1 to sqrt(n).

Hint 3

For each d that divides n, add both d and n/d to the sum. Watch the special case d == n/d (perfect square) — don't double-count.

Hint 4

Subtract n at the end (the problem excludes the number itself from the divisor sum).

Solution approach

Reveal approach

Trial division up to sqrt(n). Special-case n == 1 -> return false (1 has no proper divisors). Initialize sum = 0. For d from 1 while d * d <= n: if n % d == 0, add d to sum, and if d != n / d, also add n / d. After the loop, sum holds the count of all divisors including n itself. Return sum - n == n (which is the same as sum == 2 * n). O(sqrt(n)) time, O(1) space. Cheat sheet: known perfect numbers under 10^8 are 6, 28, 496, 8128, 33550336 — for a constant-time lookup variant, hardcode those five. The trial-division version is the interview-grade answer.

Complexity

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

Related patterns

  • math
  • number-theory

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple

Practice these live with InterviewChamp.AI

Drill Perfect Number and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →