Check If Number Is A Sum Of Powers Of Three - Leetcode Solution

Problem Statement:

The problem "Check If Number Is A Sum Of Powers Of Three" on LeetCode asks us to determine if a given number can be expressed as a sum of distinct powers of 3. In other words, are there any non-negative integers x1, x2, ..., xn, such that the given number can be represented as x1 * 3^0 + x2 * 3^1 + ... + xn * 3^(n-1), where n is the number of distinct powers of 3 in the sum.

Solution:

One thing we can observe is that any number n <= 1 is already a power of 3, and hence we can directly return True for it. For other numbers, we can start from the highest power of 3 possible that is <= n, and keep subtracting its value from n until we reach 0. If we reach 0, it means that we were able to represent n as a sum of distinct powers of 3, otherwise we cannot do so.

To implement the above approach, we can use a while loop that runs until n becomes 0 or less, and inside the loop, subtract the highest possible power of 3 from n and update the remaining values of n and the highest possible power of 3.

Here is the detailed implementation:

Step 1: Check if n is <= 1, in which case we can directly return True.

Step 2: Initialize a variable "power" to 1, which will hold the highest possible power of 3 currently available.

Step 3: Run a while loop until n becomes 0 or less. Inside the loop:

    a. Subtract the highest possible power of 3 (i.e., "power * 3") from n and store the result in n.
    
    b. Update the value of "power" to "power * 3", to get the next highest possible power of 3.
    

Step 4: If n is now 0, it means that we were able to represent the original value of n as a sum of distinct powers of 3. Hence, we can return True, else we cannot do so, and hence we return False.

Here is the Python code for the solution:

class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        
        # Step 1
        if n <= 1:
            return True
        
        # Step 2
        power = 1
        
        # Step 3
        while n >= power * 3:
            power *= 3
            n -= power
            
        # Step 4
        return n == 0

Time Complexity Analysis:

The time complexity of the solution is O(log3 n), where n is the given number. This is because in the while loop, we are subtracting the highest possible power of 3 repeatedly from n until it becomes 0 or less. Since the highest possible power of 3 is increasing by a factor of 3 each time, the number of iterations required in the while loop will be log3 n. Hence, the overall time complexity is O(log3 n).

Space Complexity Analysis:

The space complexity of the solution is O(1), as we are not using any extra space other than the variables used for storing the highest possible power of 3 and the remaining value of n.

1