Jobs

Interviews

Discussions

Perfect Number

Easy

Grammarly

1 view

Topics:

ArraysTwo Pointers

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⁸

Perfect Number

Easy

Grammarly

1 view

Topics:

ArraysTwo Pointers

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⁸

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the possible range of values for the input integer `num`? Is `num` guaranteed to be positive?
Should I handle the case where `num` is 1 or 0, and if so, what should I return in these cases?
Are there any specific performance constraints I should keep in mind given the possible range of `num`?
To confirm, a proper divisor of `num` includes 1 but excludes `num` itself, correct?
Could you clarify the expected behavior if `num` is a very large number that may result in integer overflow when summing its divisors?

Brute Force Solution

Approach

The perfect number problem asks us to determine if a number equals the sum of its divisors (excluding the number itself). The brute force method involves checking every possible number that could be a divisor.

Here's how the algorithm would work step-by-step:

Start with the number you want to test.
Consider every whole number smaller than the number you are testing, starting from 1.
For each of these smaller numbers, check if it divides the original number evenly (without any remainder).
If it does divide evenly, add it to a running total.
Once you've checked all the numbers smaller than the original number, compare the running total to the original number.
If the running total is the same as the original number, then the original number is a perfect number.

Code Implementation

def is_perfect_number(number_to_test):
    sum_of_divisors = 0

    # Iterate through all possible divisors less than the number
    for possible_divisor in range(1, number_to_test):

        # Check if the possible divisor divides evenly
        if number_to_test % possible_divisor == 0:

            # Add the divisor to the running sum
            sum_of_divisors += possible_divisor

    # Determine if the number is perfect
    if sum_of_divisors == number_to_test:
        return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through numbers from 1 up to n-1 to find divisors of the input number n. For each number i in this range, a division operation (n % i) is performed to check if i is a divisor. Since the loop runs approximately n times, where n is the input number, and each iteration involves a constant time operation, the time complexity is directly proportional to n. Therefore, the Big O notation for this solution is O(n).

Space Complexity

O(1) – The algorithm calculates the sum of divisors by iterating from 1 up to the input number (N). It only uses a few integer variables: one to store the input number, one for the current divisor being checked, and another to accumulate the sum of the divisors. Since the number of variables doesn't depend on the input size (N), the space required remains constant. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to find if a number equals the sum of its divisors (excluding itself). We can do this more efficiently than checking every number by only checking up to the square root of the given number. We leverage the fact that divisors come in pairs.

Here's how the algorithm would work step-by-step:

Begin by finding all the numbers that perfectly divide the given number.
Recognize that if a number divides evenly, there is a pair that also divides evenly (e.g., for 28, 2 and 14 are a pair).
Instead of checking all numbers up to the given number, only check up to its square root. This greatly reduces the work.
For each number that divides evenly within the square root, add both it and its corresponding pair to the sum of divisors.
Be careful to not add the square root twice, when the number is a perfect square.
Remember to exclude the number itself from the sum of its divisors.
Finally, check if the sum of the divisors equals the original number. If it does, the number is perfect.

Code Implementation

def is_perfect_number(number):    if number <= 1:
        return False

    divisor_sum = 1
    square_root = int(number**0.5)

    # Iterate up to the square root to find divisors
    for possible_divisor in range(2, square_root + 1):
        if number % possible_divisor == 0:

            #Add both divisor and its pair
            divisor_sum += possible_divisor + number // possible_divisor

            #Correct if it's a perfect square
            if possible_divisor == number // possible_divisor:
                divisor_sum -= possible_divisor

    #Subtract the number itself, as per definition.
    divisor_sum -= 0

    # Check if the sum of divisors equals the number
    return divisor_sum == number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(sqrt(n)) – The algorithm iterates up to the square root of the input number n. For each number i from 1 to sqrt(n), it performs a constant number of operations: a division check (n % i == 0), and potential addition of i and n/i to the sum of divisors. Therefore, the number of operations is proportional to the square root of n, leading to a time complexity of O(sqrt(n)).

Space Complexity

O(1) – The algorithm calculates the sum of divisors using a single variable to accumulate the sum. It also uses a variable to iterate up to the square root of the input number, N. Since these variables take up a constant amount of space regardless of the size of N, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Input number is negative	Return false immediately as perfect numbers are defined as positive integers.
Input number is zero	Return false immediately as zero is not a perfect number.
Input number is one	Return false immediately as 1 has no proper divisors, and the sum of its proper divisors is 0.
Input number is a large number that causes integer overflow when summing divisors	Use a larger integer type (e.g., long) to store the sum of divisors to prevent overflow.
Input number is a prime number	Return false immediately as a prime number has only 1 as a proper divisor, which will never equal the prime itself (except for 2 which is not prime).
Large perfect numbers can lead to performance issues due to divisor calculation	Optimize divisor calculation by only iterating up to the square root of the number.
Perfect number calculation for extremely large numbers	Consider utilizing techniques such as asynchronous processing or multithreading if the algorithm's computation time surpasses the system's limit.
No perfect number exists within a limited range.	The algorithm correctly returns false for any non-perfect number within the range of possible inputs.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the possible range of values for the input integer `num`? Is `num` guaranteed to be positive?
Should I handle the case where `num` is 1 or 0, and if so, what should I return in these cases?
Are there any specific performance constraints I should keep in mind given the possible range of `num`?
To confirm, a proper divisor of `num` includes 1 but excludes `num` itself, correct?
Could you clarify the expected behavior if `num` is a very large number that may result in integer overflow when summing its divisors?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the number you want to test.
Consider every whole number smaller than the number you are testing, starting from 1.
For each of these smaller numbers, check if it divides the original number evenly (without any remainder).
If it does divide evenly, add it to a running total.
Once you've checked all the numbers smaller than the original number, compare the running total to the original number.
If the running total is the same as the original number, then the original number is a perfect number.

Code Implementation

def is_perfect_number(number_to_test):
    sum_of_divisors = 0

    # Iterate through all possible divisors less than the number
    for possible_divisor in range(1, number_to_test):

        # Check if the possible divisor divides evenly
        if number_to_test % possible_divisor == 0:

            # Add the divisor to the running sum
            sum_of_divisors += possible_divisor

    # Determine if the number is perfect
    if sum_of_divisors == number_to_test:
        return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Begin by finding all the numbers that perfectly divide the given number.
Recognize that if a number divides evenly, there is a pair that also divides evenly (e.g., for 28, 2 and 14 are a pair).
Instead of checking all numbers up to the given number, only check up to its square root. This greatly reduces the work.
For each number that divides evenly within the square root, add both it and its corresponding pair to the sum of divisors.
Be careful to not add the square root twice, when the number is a perfect square.
Remember to exclude the number itself from the sum of its divisors.
Finally, check if the sum of the divisors equals the original number. If it does, the number is perfect.

Code Implementation

def is_perfect_number(number):    if number <= 1:
        return False

    divisor_sum = 1
    square_root = int(number**0.5)

    # Iterate up to the square root to find divisors
    for possible_divisor in range(2, square_root + 1):
        if number % possible_divisor == 0:

            #Add both divisor and its pair
            divisor_sum += possible_divisor + number // possible_divisor

            #Correct if it's a perfect square
            if possible_divisor == number // possible_divisor:
                divisor_sum -= possible_divisor

    #Subtract the number itself, as per definition.
    divisor_sum -= 0

    # Check if the sum of divisors equals the number
    return divisor_sum == number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input number is negative	Return false immediately as perfect numbers are defined as positive integers.
Input number is zero	Return false immediately as zero is not a perfect number.
Input number is one	Return false immediately as 1 has no proper divisors, and the sum of its proper divisors is 0.
Input number is a large number that causes integer overflow when summing divisors	Use a larger integer type (e.g., long) to store the sum of divisors to prevent overflow.
Input number is a prime number	Return false immediately as a prime number has only 1 as a proper divisor, which will never equal the prime itself (except for 2 which is not prime).
Large perfect numbers can lead to performance issues due to divisor calculation	Optimize divisor calculation by only iterating up to the square root of the number.
Perfect number calculation for extremely large numbers	Consider utilizing techniques such as asynchronous processing or multithreading if the algorithm's computation time surpasses the system's limit.
No perfect number exists within a limited range.	The algorithm correctly returns false for any non-perfect number within the range of possible inputs.