Jobs

Interviews

Discussions

Check if Number is a Sum of Powers of Three

Medium

Asked by:

15 views

Topics:

Bit ManipulationGreedy Algorithms

Given an integer n, return true if it is possible to represent n as the sum of distinct powers of three. Otherwise, return false.

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

Example 1:

Input: n = 12
Output: true
Explanation: 12 = 3¹ + 3²

Example 2:

Input: n = 91
Output: true
Explanation: 91 = 3⁰ + 3² + 3⁴

Example 3:

Input: n = 21
Output: false

Constraints:

1 <= n <= 10⁷

Check if Number is a Sum of Powers of Three

Medium

Asked by:

15 views

Topics:

Bit ManipulationGreedy Algorithms

Given an integer n, return true if it is possible to represent n as the sum of distinct powers of three. Otherwise, return false.

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

Example 1:

Input: n = 12
Output: true
Explanation: 12 = 3¹ + 3²

Example 2:

Input: n = 91
Output: true
Explanation: 91 = 3⁰ + 3² + 3⁴

Example 3:

Input: n = 21
Output: false

Constraints:

1 <= n <= 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 `n`? Can `n` be negative or zero?
Are the powers of three required to be strictly distinct, or can a power of three be used multiple times?
If `n` cannot be expressed as the sum of distinct powers of three, should I return false, or throw an exception?
Could you provide a few examples of inputs and their corresponding expected outputs to ensure I understand the problem correctly?
If there are multiple ways to express `n` as a sum of distinct powers of three, am I required to find a specific one, or is any valid combination sufficient?

Brute Force Solution

Approach

The core idea of a brute force approach for this problem is to explore all possible combinations of powers of three. We repeatedly subtract powers of three from the given number, seeing if we can eventually reach zero. This involves trying every combination, even if it seems inefficient.

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

First, identify a collection of powers of three that are less than or equal to the number we're checking.
Start with the largest power of three in that collection.
Try subtracting this largest power of three from our number.
If the result is zero, then the original number *is* a sum of powers of three, and we're done.
If the result is positive, continue trying to subtract other powers of three (smaller ones) from this remaining result.
If the result is negative, undo the subtraction and try not subtracting that power of three at all.
Repeat this process of trying to subtract each power of three, and then moving to smaller powers of three, in every combination.
If, after trying all the combinations, we can't reach zero, then the original number is *not* a sum of powers of three.

Code Implementation

def check_if_number_is_sum_of_powers_of_three(number_to_check):
    powers_of_three = []
    power = 1
    while power <= number_to_check:
        powers_of_three.append(power)
        power *= 3

    powers_of_three.reverse()

    def can_be_expressed(remaining_number, index):
        if remaining_number == 0:
            return True
        
        if index == len(powers_of_three):
            return False
        
        # Try subtracting the current power of three
        if remaining_number >= powers_of_three[index]:
            if can_be_expressed(remaining_number - powers_of_three[index], index + 1):
                return True

            #If subtracting doesn't work, try not subtracting.
        
        # Skip the current power of three
        return can_be_expressed(remaining_number, index + 1)

    #Start the recursive calls.
    return can_be_expressed(number_to_check, 0)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^k) – The algorithm explores all possible combinations of powers of three less than or equal to the input number 'n'. Let's say there are 'k' powers of three less than or equal to 'n'. For each of these 'k' powers, the algorithm makes a decision: either include it in the sum or exclude it. This binary choice (include/exclude) is made for each of the 'k' powers. Therefore, the total number of combinations explored is 2^k. The number of powers, k, grows logarithmically with n (since 3^k <= n, k <= log3(n)), however, the algorithm explores 2^k combinations. Thus the time complexity is O(2^k).

Space Complexity

O(log N) – The algorithm uses recursion. The maximum depth of the recursion depends on how many powers of three are less than or equal to the input number N. Since each recursive call either subtracts a power of three or skips it, the maximum depth is proportional to the number of powers of three less than or equal to N. The number of powers of three less than or equal to N is logarithmic with base 3, hence log base 3 of N. Each recursive call creates a new stack frame, so the auxiliary space is O(log N).

Optimal Solution

Approach

The problem asks if a number can be expressed as the sum of powers of three. The optimal solution involves repeatedly dividing the number by three and checking the remainders. This approach leverages the unique properties of base-3 representation to efficiently determine if the number meets the given condition.

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

Repeatedly divide the input number by 3.
Check the remainder after each division.
If the remainder is ever 2, then the number cannot be expressed as a sum of powers of three, and you can immediately return false.
If the remainder is 0 or 1, continue dividing.
If the number eventually becomes 0, it means the original number can be expressed as a sum of powers of three, so return true.

Code Implementation

def is_sum_of_powers_of_three(number):
    while number > 0:
        remainder = number % 3

        # If remainder is 2, it can't be a sum of powers of three
        if remainder == 2:
            return False

        number //= 3

    # If the number becomes 0, it is a sum of powers of three
    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The time complexity is determined by how many times the input number 'n' can be divided by 3 before it becomes 0. Each division represents a step. Since we are repeatedly dividing 'n' by 3, the number of divisions is proportional to the logarithm base 3 of 'n'. Therefore, the time complexity is O(log₃ n), which is equivalent to O(log n) because the base of the logarithm doesn't affect Big O notation.

Space Complexity

O(1) – The provided algorithm repeatedly divides the input number by 3 and checks the remainder. This process uses only a few constant space variables to store the input number (which gets modified in place) and the remainder. No additional data structures that scale with the input number are used, such as auxiliary arrays or hash maps. Therefore, the space complexity remains constant irrespective of the input number's magnitude (N), where N is the input number itself. Thus, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Input n is zero.	Return true, as zero can be expressed as an empty sum of powers of three.
Input n is a negative number.	Return false, as powers of three are always positive.
Input n is one (3^0).	Return true, as 1 is a power of three.
Input n is a large number that could lead to integer overflow if not handled carefully (e.g., near the maximum integer value).	The algorithm itself will not cause overflow as long as integer division is used and powers of 3 are less than the maximum integer value.
Input n is a power of three (e.g., 3, 9, 27).	Return true, as these directly satisfy the condition.
Input n is the sum of several different powers of three (e.g., 1+3+9=13).	The algorithm should correctly identify and return true.
Input n cannot be expressed as the sum of distinct powers of three (e.g., 2, 5, 8).	The algorithm should correctly identify and return false.
Input n requiring many iterations/divisions to determine if it's a sum of distinct powers of 3.	The algorithm's time complexity is logarithmic, so it handles even relatively large inputs efficiently as long as integer overflow isn't a concern.

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 `n`? Can `n` be negative or zero?
Are the powers of three required to be strictly distinct, or can a power of three be used multiple times?
If `n` cannot be expressed as the sum of distinct powers of three, should I return false, or throw an exception?
Could you provide a few examples of inputs and their corresponding expected outputs to ensure I understand the problem correctly?
If there are multiple ways to express `n` as a sum of distinct powers of three, am I required to find a specific one, or is any valid combination sufficient?

Brute Force Solution

Approach

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

First, identify a collection of powers of three that are less than or equal to the number we're checking.
Start with the largest power of three in that collection.
Try subtracting this largest power of three from our number.
If the result is zero, then the original number *is* a sum of powers of three, and we're done.
If the result is positive, continue trying to subtract other powers of three (smaller ones) from this remaining result.
If the result is negative, undo the subtraction and try not subtracting that power of three at all.
Repeat this process of trying to subtract each power of three, and then moving to smaller powers of three, in every combination.
If, after trying all the combinations, we can't reach zero, then the original number is *not* a sum of powers of three.

Code Implementation

def check_if_number_is_sum_of_powers_of_three(number_to_check):
    powers_of_three = []
    power = 1
    while power <= number_to_check:
        powers_of_three.append(power)
        power *= 3

    powers_of_three.reverse()

    def can_be_expressed(remaining_number, index):
        if remaining_number == 0:
            return True
        
        if index == len(powers_of_three):
            return False
        
        # Try subtracting the current power of three
        if remaining_number >= powers_of_three[index]:
            if can_be_expressed(remaining_number - powers_of_three[index], index + 1):
                return True

            #If subtracting doesn't work, try not subtracting.
        
        # Skip the current power of three
        return can_be_expressed(remaining_number, index + 1)

    #Start the recursive calls.
    return can_be_expressed(number_to_check, 0)

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:

Repeatedly divide the input number by 3.
Check the remainder after each division.
If the remainder is ever 2, then the number cannot be expressed as a sum of powers of three, and you can immediately return false.
If the remainder is 0 or 1, continue dividing.
If the number eventually becomes 0, it means the original number can be expressed as a sum of powers of three, so return true.

Code Implementation

def is_sum_of_powers_of_three(number):
    while number > 0:
        remainder = number % 3

        # If remainder is 2, it can't be a sum of powers of three
        if remainder == 2:
            return False

        number //= 3

    # If the number becomes 0, it is a sum of powers of three
    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n is zero.	Return true, as zero can be expressed as an empty sum of powers of three.
Input n is a negative number.	Return false, as powers of three are always positive.
Input n is one (3^0).	Return true, as 1 is a power of three.
Input n is a large number that could lead to integer overflow if not handled carefully (e.g., near the maximum integer value).	The algorithm itself will not cause overflow as long as integer division is used and powers of 3 are less than the maximum integer value.
Input n is a power of three (e.g., 3, 9, 27).	Return true, as these directly satisfy the condition.
Input n is the sum of several different powers of three (e.g., 1+3+9=13).	The algorithm should correctly identify and return true.
Input n cannot be expressed as the sum of distinct powers of three (e.g., 2, 5, 8).	The algorithm should correctly identify and return false.
Input n requiring many iterations/divisions to determine if it's a sum of distinct powers of 3.	The algorithm's time complexity is logarithmic, so it handles even relatively large inputs efficiently as long as integer overflow isn't a concern.