Perfect Number

Perfect Number

What is this problem about?

The Perfect Number problem asks whether a positive integer is "perfect" — equal to the sum of all its proper divisors (divisors excluding the number itself). For example, 28 = 1+2+4+7+14. This easy coding problem tests efficient divisor enumeration. The math interview pattern is demonstrated.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, and Bloomberg ask this as a math warmup that tests divisor enumeration. The key optimization: iterate only up to √n to find divisor pairs in O(√n) time instead of O(n).

Algorithmic pattern used

Divisor enumeration up to √n. For i from 2 to √n: if i divides n, add both i and n/i to the divisor sum. Handle the case i == n/i (perfect square, don't add twice). Start with sum=1 (the divisor 1 is always included). Check if sum == n. Return false for n=1 (1 is not perfect).

Example explanation

n=28. Sum starts at 1.

• i=2: 28%2=0. Add 2+14=16. Sum=17.
• i=3: 28%3≠0.
• i=4: 28%4=0. Add 4+7=11. Sum=28.
• i=5: 5²=25<28. Continue. 5 doesn't divide.
• i=5: √28≈5.29. Stop. Sum=28==n. Return true.

n=6. Sum=1+2+3=6==6. Return true.

Common mistakes candidates make

• Linear scan (O(n)) instead of O(√n).
• Including n as a divisor (must be PROPER divisors only).
• Double-counting when i == √n (e.g., n=16: i=4, 4==16/4, add only once).
• Not handling n=1 special case (1 has no proper divisors except trivially).

Interview preparation tip

Divisor enumeration up to √n is a fundamental number theory optimization. Always iterate i from 2 to sqrt(n), adding both i and n/i when i divides n, checking for the perfect square case. Practice this on: "sum of divisors," "count divisors," "perfect number check," "amicable numbers." It's a building block for all divisor-based mathematical problems.