<p>Given an integer <code>n</code>, return <code>true</code> <em>if it is possible to represent </em><code>n</code><em> as the sum of distinct powers of three.</em> Otherwise, return <code>false</code>.</p>

<p>An integer <code>y</code> is a power of three if there exists an integer <code>x</code> such that <code>y == 3<sup>x</sup></code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 12
<strong>Output:</strong> true
<strong>Explanation:</strong> 12 = 3<sup>1</sup> + 3<sup>2</sup>
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 91
<strong>Output:</strong> true
<strong>Explanation:</strong> 91 = 3<sup>0</sup> + 3<sup>2</sup> + 3<sup>4</sup>
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 21
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>7</sup></code></li>
</ul>

import math
import numpy as np


class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        # 3 ** ? == 10**7
        # the time complexity is      2      ^      [log_3(n)]              
        #      First,   we compute log_3 (n) as just some function from math                
        #math.log(n,3)

        # Previously calculated, reachable values                 
        #dict = {}

        '''
            Time complexity:   O( log_3[n] * time it takes to calculate log_3[n_curr] )
            Space complexity:  O( log_3[n] )
            Because what we're doing is just generating all the powers of 3, subtracting the biggest, and then binary searching for the next biggest in the process.    
            It's a greedy algorithm.    
            All I have to do is calculate the log_3 of the existing largest repeatedly (I could even make it recursive rather than a for loop)   
        '''

        def recurse(n):
            if n == 0:
                return True
            exponent_before_flooring = math.log(n,3)
            exponent = None # initialize
            if np.allclose(exponent_before_flooring, np.round(exponent_before_flooring), rtol = 1e-06):
                #ie. n == 243 and exponent_before_flooring == 4.999999996 because of mantissa calculation errors         
                exponent = math.ceil(exponent_before_flooring)
            else:
                exponent = math.floor(exponent_before_flooring)
            nearest_power_of_3 = 3 ** (   exponent      )       
            print(exponent)
            print(n)
            print(nearest_power_of_3)
            print("\n")
            if n >= nearest_power_of_3 * 2:
                return False
            else:
                return recurse( n - nearest_power_of_3 )


        return recurse(n)




















































































210