Jobs

Interviews

Discussions

Power of Three

Easy

Goldman Sachs

0 views

Topics:

Bit ManipulationRecursion

Given an integer n, return true if it is a power of three. Otherwise, return false.

An integer n is a power of three, if there exists an integer x such that n == 3^x.

Example 1:

Input: n = 27
Output: true
Explanation: 27 = 3³

Example 2:

Input: n = 0
Output: false
Explanation: There is no x where 3^x = 0.

Example 3:

Input: n = -1
Output: false
Explanation: There is no x where 3^x = (-1).

Constraints:

-2³¹ <= n <= 2³¹ - 1

Follow up: Could you solve it without loops/recursion?

Power of Three

Easy

Goldman Sachs

0 views

Topics:

Bit ManipulationRecursion

Given an integer n, return true if it is a power of three. Otherwise, return false.

An integer n is a power of three, if there exists an integer x such that n == 3^x.

Example 1:

Input: n = 27
Output: true
Explanation: 27 = 3³

Example 2:

Input: n = 0
Output: false
Explanation: There is no x where 3^x = 0.

Example 3:

Input: n = -1
Output: false
Explanation: There is no x where 3^x = (-1).

Constraints:

-2³¹ <= n <= 2³¹ - 1

Follow up: Could you solve it without loops/recursion?

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 range of possible integer inputs for `n`? Could `n` be negative or zero?
Should I expect `n` to always be an integer, or should I account for floating-point inputs?
If `n` is not a power of three, what should the function return (e.g., `false`, `0`, `-1`)?
Are there any specific error conditions I should handle, such as `n` being exceptionally large?
By power of three, do you mean integer powers (e.g., 3^0, 3^1, 3^2, ...), or is there any flexibility in the exponent?

Brute Force Solution

Approach

To check if a number is a power of three using brute force, we repeatedly divide the number by 3 until we get 1 or something that is not divisible by 3. If we eventually reach 1, the original number was a power of three.

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

Start with the number you want to test.
Check if the number is equal to one. If it is, you are done, and the answer is yes (it is a power of three).
If the number is not equal to one, check if the number is divisible by three.
If it is divisible, divide the number by three and repeat the process from step two using this new result.
If it is not divisible by three, you are done, and the answer is no (it is not a power of three).

Code Implementation

def is_power_of_three_brute_force(number_to_test):
    # Check if the number is valid
    if number_to_test <= 0:
        return False

    while True:
        # If the number equals one, it is a power of three
        if number_to_test == 1:
            return True

        # Check if the number is divisible by three
        if number_to_test % 3 == 0:

            number_to_test = number_to_test / 3

        # If not divisible by three, it's not a power of three
        else:

            return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The provided algorithm repeatedly divides the input number n by 3 in each iteration of the loop. The loop continues until n becomes 1 or is no longer divisible by 3. The number of divisions required is proportional to the base-3 logarithm of n. Therefore, the time complexity is logarithmic with a base of 3, which is written as O(log₃ n). However, in Big O notation, the base of the logarithm is irrelevant, so we simplify it to O(log n).

Space Complexity

O(1) – The provided algorithm iteratively divides the input number by 3. It only requires a constant amount of extra space to store the number being checked and potentially a boolean variable to track the result. The number of iterations depends on the input value, but the space used doesn't grow with the input size (N, the input number itself). Therefore, the auxiliary space complexity is O(1), indicating constant space usage.

Optimal Solution

Approach

The goal is to determine if a given number is a power of three. Instead of repeated division or multiplication, we can leverage the properties of powers of three and integer limits to quickly check if the number is a power of three.

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

Find the largest possible power of three that can be represented as a standard integer.
Check if the largest power of three is divisible by the given number.
If it is divisible, then the given number is a power of three; otherwise, it is not.

Code Implementation

def is_power_of_three(number):
    if number <= 0:
        return False

    largest_power_of_three = 3**19

    # Find largest power of 3 within integer limits.

    # Check divisibility to determine if it's a power of 3.
    if largest_power_of_three % number == 0:
        return True
    else:
        return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The provided solution calculates the largest power of three representable as an integer, which is a constant-time operation. It then performs a single division to check divisibility. Since these are constant-time operations that do not depend on the input number 'n', the overall time complexity is O(1).

Space Complexity

O(1) – The provided solution calculates the largest possible power of three within the integer limits and stores it in a variable. It then performs a divisibility check. No auxiliary data structures, such as lists or hash maps, are used. Therefore, the space complexity is constant, independent of the input number.

Edge Cases

Case	How to Handle
Input is zero	Return false immediately as 3 raised to any integer power is never zero.
Input is negative	Return false immediately as 3 raised to any integer power is never negative.
Input is a non-integer	The problem specifies an integer input, so either cast to int (if appropriate) or reject the input if it's non-integral.
Input is 1	Return true, as 3 to the power of 0 is 1.
Input is the maximum integer value	Check if the maximum integer value is a power of three; the iterative approach may take a long time, so a lookup table or modulo operation may be preferred.
Integer overflow during calculation	If using an iterative or recursive approach, be wary of integer overflow; use a long data type or a modulo operation against a power of 3 to prevent issues.
Floating-point precision errors	If using logarithms, account for floating point precision errors by allowing a small tolerance when comparing against an integer.
Input is a large power of 3 that exceeds typical integer limits	Using a precomputed maximum power of 3 within integer bounds helps avoid overflow and reduces computation.

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 range of possible integer inputs for `n`? Could `n` be negative or zero?
Should I expect `n` to always be an integer, or should I account for floating-point inputs?
If `n` is not a power of three, what should the function return (e.g., `false`, `0`, `-1`)?
Are there any specific error conditions I should handle, such as `n` being exceptionally large?
By power of three, do you mean integer powers (e.g., 3^0, 3^1, 3^2, ...), or is there any flexibility in the exponent?

Brute Force Solution

Approach

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

Start with the number you want to test.
Check if the number is equal to one. If it is, you are done, and the answer is yes (it is a power of three).
If the number is not equal to one, check if the number is divisible by three.
If it is divisible, divide the number by three and repeat the process from step two using this new result.
If it is not divisible by three, you are done, and the answer is no (it is not a power of three).

Code Implementation

def is_power_of_three_brute_force(number_to_test):
    # Check if the number is valid
    if number_to_test <= 0:
        return False

    while True:
        # If the number equals one, it is a power of three
        if number_to_test == 1:
            return True

        # Check if the number is divisible by three
        if number_to_test % 3 == 0:

            number_to_test = number_to_test / 3

        # If not divisible by three, it's not a power of three
        else:

            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:

Find the largest possible power of three that can be represented as a standard integer.
Check if the largest power of three is divisible by the given number.
If it is divisible, then the given number is a power of three; otherwise, it is not.

Code Implementation

def is_power_of_three(number):
    if number <= 0:
        return False

    largest_power_of_three = 3**19

    # Find largest power of 3 within integer limits.

    # Check divisibility to determine if it's a power of 3.
    if largest_power_of_three % number == 0:
        return True
    else:
        return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is zero	Return false immediately as 3 raised to any integer power is never zero.
Input is negative	Return false immediately as 3 raised to any integer power is never negative.
Input is a non-integer	The problem specifies an integer input, so either cast to int (if appropriate) or reject the input if it's non-integral.
Input is 1	Return true, as 3 to the power of 0 is 1.
Input is the maximum integer value	Check if the maximum integer value is a power of three; the iterative approach may take a long time, so a lookup table or modulo operation may be preferred.
Integer overflow during calculation	If using an iterative or recursive approach, be wary of integer overflow; use a long data type or a modulo operation against a power of 3 to prevent issues.
Floating-point precision errors	If using logarithms, account for floating point precision errors by allowing a small tolerance when comparing against an integer.
Input is a large power of 3 that exceeds typical integer limits	Using a precomputed maximum power of 3 within integer bounds helps avoid overflow and reduces computation.