1780: Check-if-Number-is-a-Sum-of-Powers-of-Three
Medium

table of contents

I saw 2 solutions.

The first one was to repeatedly subtract the largest power of 3 from n, and then:

code

class Solution {
public:
    bool checkPowersOfThree(int n) {
        for (int i = ceil(log(n)/log(3)); i >= 0; --i) {
            if (n >= pow(3, i)) {
                n -= pow(3, i);
            }
        }
        if (n == 0) {
            return true;
        }
        return false;
    }
};

complexity

The other solution was to just repeatedly divide n by 3; if n is made up of only powers of 3, then the remainder of n/3 should always be either 0 or 1.

Therefore, to see if n is made up of only powers of 3, we can just check n % 3 and repeatedly floor divide n until we get n%3 == 2, where we return false, or until n == 0, where we return true.

Code:

class Solution {
public:
    bool checkPowersOfThree(int n) {
        while (n > 0) {
            int remainder = n%3;
            if (remainder == 2) {
                return false;
            }
            n /= 3;
        }
        return true;
    }
};

complexity

time taken