Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1780.html
1780. Check if Number is a Sum of Powers of Three
Level
Medium
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 == 3^x.
Example 1:
Input: n = 12
Output: true
Explanation: 12 = 3^1 + 3^2
Example 2:
Input: n = 91
Output: true
Explanation: 91 = 3^0 + 3^2 + 3^4
Example 3:
Input: n = 21
Output: false
Constraints:
1 <= n <= 10^7
Solution
The integer n can always be converted into a base three representation. Each digit in base three representation is 0, 1 or 2. To represent n as the sum of distinct powers of three, each digit in base three representation must be 0 or 1.
In this problem, we do not actually convert n into a base three representation. We only need to calculate the digits and we do not care the order of the digits. Therefore, while n > 0, calculate the n % 3 each time and if a remainder 2 is found, return false. Otherwise, let n = n / 3 and repeat the process until n becomes 0. If n becomes 0 without any remainder 2 met, return true.
-
class Solution { public boolean checkPowersOfThree(int n) { while (n > 0) { int remainder = n % 3; if (remainder == 2) return false; n /= 3; } return true; } } ############ class Solution { public boolean checkPowersOfThree(int n) { while (n > 0) { if (n % 3 > 1) { return false; } n /= 3; } return true; } } -
// OJ: https://leetcode.com/problems/check-if-number-is-a-sum-of-powers-of-three/ // Time: O(log_3^N) // Space: O(1) class Solution { public: bool checkPowersOfThree(int n) { while (n % 3 == 0 || (n % 3 == 1 && n != 1)) { if (n % 3 == 1) n -= 1; n /= 3; } return n == 1; } }; -
class Solution: def checkPowersOfThree(self, n: int) -> bool: while n: if n % 3 > 1: return False n //= 3 return True ############ # 1780. Check if Number is a Sum of Powers of Three # https://leetcode.com/problems/check-if-number-is-a-sum-of-powers-of-three/ class Solution: def checkPowersOfThree(self, n: int) -> bool: while n > 1: if n % 3 == 2: return False n //= 3 return n == 1 -
func checkPowersOfThree(n int) bool { for n > 0 { if n%3 > 1 { return false } n /= 3 } return true } -
function checkPowersOfThree(n: number): boolean { while (n) { if (n % 3 > 1) return false; n = Math.floor(n / 3); } return true; }