Post

1889 Check If Number Is A Sum Of Powers Of Three

Posted Updated
By Anurag
1 min read
1889 Check If Number Is A Sum Of Powers Of Three

Check if Number is a Sum of Powers of Three image

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:

1
2
3
4
5

**Input:** n = 12
**Output:** true
**Explanation:** 12 = 31 + 32

Example 2:

1
2
3
4
5

**Input:** n = 91
**Output:** true
**Explanation:** 91 = 30 + 32 + 34

Example 3:

1
2
3
4

**Input:** n = 21
**Output:** false

 

Constraints:

1

1 <= n <= 107

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        
        mp = set()
        cache = {}

        def recurse(n, mp):
            if n < 0:
                return False
            #print(cache)
            if n in cache:
                return cache[n]
            if n == 0:
                return True
            
            k = 0
            while math.pow(3,k) <= n:
                if k in mp:
                    k += 1
                    continue
                mp.add(k)
                if recurse(n-math.pow(3,k) , mp):
                    cache[n] = True
                    return True
                mp.remove(k)
                k += 1
            cache[n] = False
            return False
        res = recurse(n, mp)
        #print(cache)
        return res
leetcode
python
This post is licensed under CC BY 4.0 by the author.