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 <= 10^7
The description was taken from https://leetcode.com/problems/check-if-number-is-a-sum-of-powers-of-three/.
#O(Log3(N)) Time, O(1) Space
class Solution:
def checkPowersOfThree(self, n: int) -> bool:
while n:
quotient = n // 3
remainder = n % 3
if remainder == 2:
return False
n = quotient
return TrueThis problem utilizes a sort of trick.
The problem revolves around the number three, which we know is odd.
The given number doesn't have to be evenly divided into three but it needs to be evenly divided into powers of three.
From there, we may think to divide the input number by three to see if it divides evenly. However, that wouldn't work because, for example, twenty-one would satisfy that constraint but twenty-one is not a sum of exclusive powers of three.
What do we know about products of three though? Each product of three is an odd number.
To solve this problem, we can continuously divide the input number by three and look at the number left over.
If we divide a number by three, then we are only left with three numbers that would be left over.
We would either have zero if the number divides evenly, one if the number didn't, but that is okay because one is the zeroth power of three, and two, which is not okay because that is not a power of three.
While the number isn't zero, we will keep dividing.
while n:
We will take a quotient by dividing the number by three, and a remainder by using the modulo operator on the number and three.
quotient = n // 3
remainder = n % 3
If that remainder is two, we will return false.
if remainder == 2:
return False
Otherwise, we will set the input number to the quotient.
n = quotient
If we were able to continuously divide the number by three and never got two, we will return true.
return True