1780. Check if Number is a Sum of Powers of Three
Description
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 == 3x
.
Example 1:
Input: n = 12 Output: true Explanation: 12 = 31 + 32
Example 2:
Input: n = 91 Output: true Explanation: 91 = 30 + 32 + 34
Example 3:
Input: n = 21 Output: false
Constraints:
1 <= n <= 107
Solutions
Solution 1: Mathematical Analysis
We find that if a number $n$ can be expressed as the sum of several "different" powers of three, then in the ternary representation of $n$, each digit can only be $0$ or $1$.
Therefore, we convert $n$ to ternary and then check whether each digit is $0$ or $1$. If not, then $n$ cannot be expressed as the sum of several powers of three, and we directly return false
; otherwise, $n$ can be expressed as the sum of several powers of three, and we return true
.
The time complexity is $O(\log_3 n)$, and the space complexity is $O(1)$.
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 |
|