By Long Luo

Here shows 3 Approaches to slove this problem: Tricky, Recursion and Base 3 Convertion.

Brute Froce

This method is tricky.

We can easy get a table that recorded all the numbers using $\texttt{Math.power}(3, n)$ between $1$ to $10^7$.

Then scanning from the largest to the smallest, if find a value smaller or equal to $n$, then subtract it from $n$.

Repeat it until to $0$.

Analysis

• Time Complexity: $O(1)$
• Space Complexity: $O(1)$

Base 3 Conversion

As the sum of distinct powers of $3$, which means if we convert n to a base $3$, every certain position can only be $0$ or $1$.

Analysis

• Time Complexity: $O(logn)$
• Space Complexity: $O(1)$

Recursion

We can make our code more clean. Just One Line Is Enough!

Analysis

• Time Complexity: $O(logn)$
• Space Complexity: $O(1)$

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗