Power of Three

The task is to check if a given integer ( n ) is a power of three. We can solve this problem by repeatedly dividing ( n ) by 3 until we either reach 1 (which means ( n ) is a power of three) or we encounter a value that is not divisible evenly by 3 (which means ( n ) is not a power of three).

1
2
3
4
5
6
7
8
9

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False

        while n % 3 == 0:
            n //= 3

        return n == 1

Explanation

  • We start by checking if ( n ) is less than or equal to 0, in which case it cannot be a power of three, and we return False.
  • Next, we use a loop to keep dividing ( n ) by 3 as long as it is divisible by 3 (i.e., the remainder n % 3 is 0).
  • If at the end of the loop ( n ) is equal to 1, we know that the original value was a power of three, and we return True. Otherwise, we return False.

Key Insights

  • Powers of three can be identified by repeatedly dividing by 3.
  • Negative numbers and zero cannot be powers of three.

The time complexity of this code is ( O(\log n) ), where ( n ) is the given input number, and the space complexity is ( O(1) ).

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

from math import log

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        """
        :type n: int
        :rtype: bool
        """
        # Since error exist, can't use float.is_integer() to check
        # So I choose to check it back
        if n <= 0: return False
        res = round(log(n, 3))

        return 3**res == n

Problem Classification

This can be classified under the following categories:

  1. Mathematics and Number Theory: The problem is essentially asking to identify if a given number is a power of another number, which requires understanding of concepts from mathematics and number theory.

  2. Integer Manipulation: The problem deals with integer numbers and determining if they are powers of three, which requires manipulation and operation on integers.

  3. Conditional Logic and Return Statements: The solution requires returning true or false based on a condition - whether the input integer is a power of three or not. This involves understanding of conditional logic and correct use of return statements.

  4. Exponentiation and Logarithms: The problem implicitly requires understanding of the concepts of exponentiation and logarithms, as it requires determining if a number is a power of three (which is a logarithm-related concept).

Language Agnostic Coding Drills

Here’s the breakdown of the problem:

  1. Understanding the problem statement: The first step is to understand what the problem is asking for. In this case, you’re given an integer and asked to determine whether it’s a power of three.

  2. Handling edge cases: If the number is less than or equal to zero, it cannot be a power of three. Therefore, we immediately return False for such cases.

  3. Understanding the logarithm: The log base 3 of a number gives the power to which 3 must be raised to get the number. For example, if n is 9, log base 3 of 9 gives 2, because 3 raised to the power of 2 equals 9. In the context of the problem, this understanding helps you determine if a number is a power of three.

  4. Rounding the result: In the real world, logarithmic operations on integers may not result in integers due to precision issues. Therefore, the result of the logarithmic operation is rounded to the nearest integer.

  5. Checking the result: After finding the power to which 3 must be raised to get the number (or the closest estimate), you raise 3 to this power. If the result equals the original number, it indicates that the number is a power of three.

  6. Returning the result: Finally, return True if the number is a power of three, else False.

Arranged drills in increasing order of difficulty:

  1. Understanding and using conditional statements.
  2. Manipulating integers.
  3. Using logarithms and understanding their properties.
  4. Understanding precision issues with floating point numbers.
  5. Rounding numbers.
  6. Combining all of these to solve the problem.

Targeted Drills in Python

  1. Understanding and using conditional statements:

    This drill would involve coding up simple if-else statements. Here’s a simple example:

    1
2
3
4
5
6
7
8

    def is_positive(num):
    if num > 0:
        return True
    else:
        return False

print(is_positive(5))  # True
print(is_positive(-3))  # False

  2. Manipulating integers:

    This drill can involve simple mathematical operations on integers like addition, subtraction, multiplication, and division.

    1
2
3
4

    def multiply_nums(a, b):
    return a * b

print(multiply_nums(3, 4))  # 12

  3. Using logarithms and understanding their properties:

    In this drill, you can practice using the log function from the math module. You can write a function that computes the log base 2 of a number, for instance.

    1
2
3
4
5
6

    from math import log

def log_base_two(num):
    return log(num, 2)

print(log_base_two(8))  # 3.0

  4. Understanding precision issues with floating point numbers:

    For this drill, you can write a function that divides two numbers and prints the result. You will see that the result might not always be precise due to floating point precision issues.

    1
2
3
4

    def divide_nums(a, b):
    return a / b

print(divide_nums(10, 3))  # 3.3333333333333335

  5. Rounding numbers:

    This drill involves rounding off numbers using the round function.

    1
2
3
4

    def round_num(num):
    return round(num)

print(round_num(3.7))  # 4

  6. Combining all of these to solve the problem:

    Finally, once you are comfortable with all the above drills, you can proceed to write the solution to the problem.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10

    from math import log

def is_power_of_three(n):
    if n <= 0:
        return False
    res = round(log(n, 3))
    return 3**res == n

print(is_power_of_three(9))  # True
print(is_power_of_three(10))  # False