Check if Number is a Sum of Powers of Three

Leetcode Problem:

• Check if Number is a Sum of Powers of Three

Summary

• Check if a number can be represented as the sum of distinct powers of three.

Approach

• The approach used is to generate a set of powers of three up to the given number, and then try to subtract each power from the number
• If the number can be reduced to zero, it means that the number can be represented as the sum of distinct powers of three.

Complexity

• O(log n) because the number of powers of three is logarithmic to the given number n.

Explanation

• The code generates a set of powers of three up to the given number n
• It then tries to subtract each power from n
• If n can be reduced to zero, it means that n can be represented as the sum of distinct powers of three
• The time complexity is O(log n) because the number of powers of three is logarithmic to n
• This is because each power of three is 3 times the previous one, so the number of powers grows logarithmically with n.

Solution Code:

class Solution {
public:
    
    bool checkPowersOfThree(int n) {
        vector powerSet;
        int pow = 1;
        while(pow <= n){
            powerSet.push_back(pow);
            pow *= 3;
        }
        for(int i = powerSet.size() - 1; i >= 0; i--){
            if(n > powerSet[i]){
                n -= powerSet[i];
            } else if (n < powerSet[i]){
                continue;   
            } else{
                return true;
            }
        }
        return false;
    }
};