Check if Number is a Sum of Powers of Three - Leetcode 1780 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
7:40 - Coding Explanation
9:40 - Drawing Explanation 2
17:05 - Coding Explanation 2

leetcode 1780

#neetcode #leetcode #python

[Ananthrk]

Small correction around 5:40 - 13 is possible (1 + 3 +9). But other than that, great video!

[sudarsh]

Found this to be more elegant and simple solution
while (n > 1) {
int r = n % 3;
if (r == 2)
return false;
n /= 3;
}

return true;

[gabrielfonseca]

My approach was to convert it into a base 3 representation and check if any of the numbers are 2. I think this approach works because every number has exactly one base 3 representation (similar to binary) and each digit is a power of 3

[aakashbolisetty]

Damm, my first instinct was the math approach!

[anonanon]

The same problem but rephrased:
Given a number n, return true if n can be written in base-3 using only digits 1 and 0.

[jamestwosheep]

I did the math approach the lazy way given that they explicitly mention in the constraints to this problem that the largest n in their test cases is 10^7. 3^15 exceeds this limit, so 3^14 is the largest power of 3 possible. So I didn't even bother finding the largest 3^i <= n and instead just hardcoded in 14 for i. While my solution technically has O(1) run time complexity, it's a little less efficient than the solution in the video. 😅

[sekhaisemarito]

My first approach was similar to the math one, however I used log of 3 to subtract the powers instead of using the i while loop

[SandeepWithAI]

Thanks dude for explaining the mathy way of solving the proble.. you are really a math wizard.

[oldmajor]

Another interesting thing I'd like to share is that in base 2 the divisbility rules are not the same. It can be shown that a number in base 2 is congruent to its alternating digit sum mod 3.
@cache
def mod3(n):
parity=False
res=0
while n:
res += n&1 if not parity else - (n&1)
n >>=1
parity = not parity
while res < 0:
res+=3
return res if res < 3 else mod3(res)

[LasTCursE]

Considering the problem constraints it roughly equals that at best you will have 15-ish powers of 3, which at the worst case means 32767 combinations (most of which you pre-filter out since you don't need powers greater than n itself), therefor you can just brute force it..

1: Generate all powers that are less than n
2: Generate all combinations with those and put them in a Set
3: Check if n exists in that set, else return false

[shahukor]

I actually used an array to store all the possible 3^i <= n, works great too
class Solution:
def checkPowersOfThree(self, n: int) -> bool:
base = 1
i = 1
possiblebases = []

while base<=n:
possiblebases.append(base)
base = 3**i
i+=1

for j in range(len(possiblebases)-1, -1, -1):
if possiblebases[j]<=n:
n-=possiblebases[j]

return n==0

[mzeeqazi]

while n :
q, r = divmod(n, 3)
if r==2:
return False
n = q

return True

isn't this enough considering the constrain;
1 <= n <= 10^7

[sheik-tlvu]

mine

# Find the maximum power
max = 0
num = n
while num > 0:
max += 1
num -= (3 ** max)

def dfs(start, number):
if number == 0:
return True
if number < 0:
return False
for x in range(start, max + 1):
new_number = number - (3 ** x)
if dfs(x + 1, new_number):
return True

return False

return dfs(0, n)

[qulinxao]

class Solution: def checkPowersOfThree(self, n: int) -> bool:
def d(n):
while n: n, d=divmod(n, 3); yield d
return not any(2==a for a in d(n))

[asmahamdym]

I think the math solution could be simpler, this is mine:
while n > 1:
if n % 3 != 1 and n%3 != 0:
return False
n /= 3
return True

[abhishek.p]

I solved this problem by looking hint. But my thought process was, We can represent any number in sum of powers of 2 like binary number system (0, 1). lets say for converting 1010 to decimal we will raise the position of bits to 2 and multiply with the bit from right to left in this example 2^3 * 1 + 2^1 * 1 = 10 here the possible values are 0 and 1 so no matter what the number is the sum of powers will be distinct but in ternary representation (base of 3) has possible values 0, 1, 2 some number may require to use same power again to form the given number eg: 21 -> 210 3^2 will be used twice to form 21. So while converting the given number to base 3 if we encounter 2 we can return false.

[araneuskyuro]

Is using
"return backtrack(i + 1, cur + 3 ** i) or backtrack(i + 1, cur)"

Less efficient than
"if backtrack(i + 1, cur + 3**i):
return
return backtrack(i + 1, cur)" ??

[SandeepWithAI]

it would be great if you made a math course for dsa he he.. lol

[prajwals]

Man todays question was a curve ball
"distinct powers of three" this should have been in the title

[sourcerer]

I thought it's a DP problem like 416 Partition Equal Subset Sum, but TLE.