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.

Description Solution Video 9:40

507. Perfect Number

Easy50.6% acceptance8 companies

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 <= 10⁸

Asked at 8 companies

Fallible Grammarly Accenture

Google Microsoft Bloomberg Amazon Meta

Topics

Math

9:40

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

507. Perfect Number

Asked at 8 companies

Topics

Similar problems