# Problem Statement Given an integer `n`, return `true` _if it is possible to represent_ `n` _as the sum of distinct powers of three._ Otherwise, return `false`. An integer `y` is a power of three if there exists an integer `x` such that `y == 3^x`. ## Constraints - `1 <= n <= 10^7` # Solution We can declare an array containing all powers of three up until `10^7`. This array is only `15` elements, so we can use a $2^n$ [[Bitmask|bitmask]] brute force approach to just try all combinations of powers of three ```python powThrees = [3**i for i in range(15)] for mask in range(2**15): ans = 0 for j in range(15): if (1<<j) & mask: ans += powThrees[j] if ans == n: return True return False ``` Time Complexity: O$(2^{\log n})$ | Space Complexity: O$\log n$