Skip to content

← leetcode

Check if Number is a Sum of Powers of Three

· Medium

LeetCode problem 1780

I saw 2 solutions.

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

  • if n == 0, then we know that n was made up of only powers of 3
  • if n != 0, then we know that n was not made up only of powers of 3

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

  • Time: O(log n)
  • Space: O(1)

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: O(log n)
  • Space: O(1)

time taken

  • 4 minutes and 25.71 seconds