Solution Explanation: Check if Number is a Sum of Powers of Three

This problem asks whether a given integer n can be represented as the sum of distinct powers of three (e.g., 30, 31, 32, etc.). The efficient solution leverages the properties of the ternary (base-3) number system.

Core Idea:

If a number can be expressed as a sum of distinct powers of three, its ternary representation will only contain digits 0 and 1. This is because each digit in the ternary representation corresponds to a power of three. If a digit is greater than 1, it means that power of three is used more than once, violating the "distinct powers" constraint.

Algorithm:

1. Iterative Ternary Conversion: The algorithm repeatedly divides the number n by 3. The remainder is examined:

   • If the remainder is 0 or 1, it's valid (the digit in the ternary representation is 0 or 1).
   • If the remainder is 2, it's invalid (the digit is 2, indicating a power of three is used more than once). The function immediately returns false.

2. Iteration Continues: The division by 3 continues until n becomes 0. If the loop completes without finding any remainder of 2, it means all digits in the ternary representation are 0 or 1, and the function returns true.

Time Complexity: O(log3n)

The number of iterations in the while loop is proportional to the number of digits in the ternary representation of n. The number of digits in base-3 is logarithmic with respect to the number in base-10 (log3n).

Space Complexity: O(1)

The algorithm uses a constant amount of extra space, regardless of the input size.

Code Examples (with explanations):

Python:

class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        while n:
            if n % 3 > 1:  # Check if remainder is greater than 1 (invalid)
                return False
            n //= 3       # Integer division to get the next ternary digit
        return True       # All digits were 0 or 1

Java:

class Solution {
    public boolean checkPowersOfThree(int n) {
        while (n > 0) {
            if (n % 3 > 1) { // Check for invalid remainder
                return false;
            }
            n /= 3; // Integer division
        }
        return true;
    }
}

C++:

class Solution {
public:
    bool checkPowersOfThree(int n) {
        while (n) {
            if (n % 3 > 1) return false; // Check for invalid remainder
            n /= 3; // Integer division
        }
        return true;
    }
};

Go:

func checkPowersOfThree(n int) bool {
	for n > 0 {
		if n%3 > 1 { // Check for invalid remainder
			return false
		}
		n /= 3 // Integer division
	}
	return true
}

TypeScript:

function checkPowersOfThree(n: number): boolean {
    while (n > 0) {
        if (n % 3 > 1) return false; //Check for invalid remainder
        n = Math.floor(n / 3); // Integer division
    }
    return true;
}

All the code examples above follow the same core logic: iterative ternary conversion and checking for invalid remainders. They differ only in syntax due to the specific language used.