Perfect Number

We can approach this problem by finding the divisors of a given number and then checking if the sum of the divisors is equal to the number itself. To find the divisors, we can iterate from 1 to the square root of the number and add both divisors when we find a pair. If the sum is equal to the original number, then we return True, otherwise, we return False.

Here is the solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num <= 1:
            return False

        divisors_sum = 1  # Start from 1 because all numbers are divisible by 1
        i = 2  # Start from 2 because we've already included 1

        while i * i <= num:
            if num % i == 0:
                # If the divisors are the same, add it only once.
                # Else add both
                if i * i == num:
                    divisors_sum += i
                else:
                    divisors_sum += i + num // i
            i += 1

        # If the sum of divisors is equal to the number, it's a perfect number
        return divisors_sum == num

This solution starts by checking if the number is less than or equal to 1. If it is, it returns False because no number in that range can be perfect. It then initializes the sum of divisors to 1 and begins checking for divisors from 2 up to the square root of the number. If a divisor is found, it is added to the sum, and if the divisor pair are different, both are added. After checking all possible divisors, it compares the sum with the original number and returns True if they are equal, indicating that the number is perfect.

1
2
3
4
5
6
7
8
9

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num == 1:
            return False
        res = 1
        for i in range(2,int(num**0.5)+1):
            if num%i == 0:
                res += i + num//i
        return res == num

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num == 1) return false;

        int sum = 0;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                sum += i + num / i;
            }
        }
        sum++;

        return sum == num;
    }
}

The Java function that checks if a given number is a “perfect number”. A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself.

Here is a step-by-step explanation of the code:

  1. The function checkPerfectNumber takes an integer num as its argument.

  2. If num is 1, the function immediately returns false, because 1 is not a perfect number.

  3. An integer variable sum is initialized with 0. This variable will hold the sum of the divisors of num.

  4. A for loop iterates over all integers i from 2 to the square root of num. This range covers all possible divisors of num.

  5. If num is divisible by i (i.e., num % i == 0), then i and the corresponding co-factor (num / i) are both divisors of num. These two divisors are added to sum.

  6. After the loop, 1 is added to sum. This is because 1 is a divisor of all numbers but was not included in the for loop.

  7. Finally, the function checks if sum is equal to num. If they are equal, num is a perfect number, so the function returns true. Otherwise, num is not a perfect number, so the function returns false.

This function only works correctly for numbers greater than 1. If num is 0 or a negative number, the function will not return the correct result.

Here’s the Python equivalent:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import math

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num == 1:
            return False

        sum = 0
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                sum += i + num // i

        sum += 1

        return sum == num

In this Python 3 version, the code essentially remains the same. The Math.sqrt(num) from Java is replaced with math.sqrt(num) in Python. Also, note that integer division is represented with // in Python as opposed to / in Java, which performs floating-point division.

Problem Classification

The problem falls into the domain of Mathematics and Number Theory. It requires knowledge of factors and perfect numbers.

‘What’ Components:

  • A perfect number definition: A positive integer that is equal to the sum of its positive divisors, excluding the number itself.
  • The concept of a divisor: An integer that can divide another integer evenly.
  • The task: Given an integer n, the task is to determine whether this number is a perfect number.

This problem can be classified as a decision problem, as the main task involves making a binary decision: whether the given number is a perfect number or not. The problem-solving involves finding the factors of the given number, summing them, and then comparing this sum with the original number. These tasks encompass aspects of computational mathematics and require algorithmic thinking to solve efficiently.

Language Agnostic Coding Drills

  1. Dissecting the Code: The code contains the following concepts:

    • Variable Initialization: Initialize certain values (in this case, res).
    • Control Flow: Check conditions using if statements.
    • Loops: Use a for loop to iterate over a range of values.
    • Mathematical Operations: Perform addition, division, modulo operations, and the square root calculation.
    • Boolean Operations: Evaluate and return a boolean value.
    • Function Definitions: Define a method within a class to perform the task.

  2. Coding Concepts or Drills (listed in order of increasing difficulty):

    • Variable Initialization: This is a basic concept involving the creation and assignment of a variable. It’s the easiest because it’s the most fundamental concept that all programming revolves around.
    • Boolean Operations: This involves checking if two values are equal. It’s slightly more complex than initialization because it involves comparison between two values.
    • Control Flow: This involves making decisions based on conditions. It’s a bit more complex as it requires understanding of how program flow can change based on certain conditions.
    • Mathematical Operations: This involves performing mathematical computations like addition, division, modulo operations, and square root calculations. It requires understanding of how these operations can be performed in a programming context.
    • Loops: This involves iterating over a range of values. It’s slightly more complex because it requires understanding of iteration and control flow.
    • Function Definitions: This involves defining a function that performs the task. It’s the most complex in this list as it requires understanding of how to encapsulate functionality within a function.

  3. Problem-Solving Approach: The problem requires finding the sum of all positive divisors of a number and checking if the sum is equal to the number itself. The following steps contribute to the solution:

    • First, a special case where the number is 1 is checked, and False is immediately returned if true because 1 is not a perfect number by definition.
    • Then, the process of finding the divisors of the number begins. It is known from number theory that the divisors of a number n occur in pairs, and one of them is less than or equal to the square root of n. Therefore, we only need to iterate up to the square root of n.
    • For each number in this range, it is checked if it is a divisor of n (i.e., n modulo this number equals 0). If it is, the number and its corresponding pair (n divided by the number) are added to the sum of the divisors.
    • Finally, after finding the sum of all divisors, it is checked if the sum is equal to the original number. If it is, the function returns True, otherwise it returns False.

    This approach effectively checks whether a number is perfect or not by leveraging mathematical properties to reduce the computational complexity.

Targeted Drills in Python

  • Variable Initialization:
1
2

# We can initialize a variable with a desired value.
x = 5
  • Boolean Operations:
1
2
3
4

# We can compare two variables and this will return a boolean value.
x = 5
y = 10
print(x == y)  # This will print False
  • Control Flow:
1
2
3
4

# We can use if statements to control the flow of our program.
x = 5
if x == 5:
    print('x is 5')  # This will print 'x is 5'
  • Mathematical Operations:
1
2
3
4
5
6
7

# We can perform various mathematical operations.
x = 5
y = 2
print(x + y)  # This will print 7
print(x // y)  # This will print 2
print(x % y)  # This will print 1
print(x**0.5)  # This will print 2.23606797749979
  • Loops:
1
2
3

# We can use loops to iterate over a range of values.
for i in range(5):
    print(i)  # This will print numbers from 0 to 4
  • Function Definitions:
1
2
3
4
5

# We can define our own functions to perform specific tasks.
def greet(name):
    return f"Hello, {name}!"

print(greet("Alice"))  # This will print 'Hello, Alice!'

Problem-Specific Concepts:

  • Finding Divisors and Summing Them: To solve our problem, we need to find the divisors of a number and sum them up. Here’s a simple drill to practice this concept:
1
2
3
4
5
6
7
8

num = 6
divisors_sum = 1
for i in range(2, int(num**0.5) + 1):
    if num % i == 0:
        divisors_sum += i
        if i != num // i:  # To avoid adding the same divisor twice in case of perfect squares
            divisors_sum += num // i
print(divisors_sum)  # This will print 6

Integrating the Drills:

To solve the problem, we first initialize the res variable to 1, as 1 is always a divisor of a number. Then, we iterate from 2 to the square root of num, checking each time if the current number is a divisor of num. If it is, we add both the current number and its corresponding pair to res. Once we’ve found and summed up all the divisors, we compare res to num using a boolean operation and return the result. We also handle the special case where num is 1 at the beginning. This can be thought of as combining all the above drills in the order of their occurrence in the original code.