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
Solution: Greedy + Math
Find the largest 3^x that <= n, subtract that from n and repeat the process.
x should be monotonically decreasing, otherwise we have duplicate terms.
e.g. 12 = 32 + 31 true
e.g. 21 = 32 + 32+ 31 false
Time complexity: O(logn?)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: bool checkPowersOfThree(int n) { int last = INT_MAX; while (n) { int p = 0; int cur = 1; while (cur * 3 <= n) { cur *= 3; ++p; } if (p == last) return false; last = p; n -= cur; } return true; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment