<jupyter_start><jupyter_text>pow(x,n)<jupyter_code># recursion
def myPow( x, n):
    """
    :type x: float
    :type n: int
    :rtype: float

    """
    N = n
    if (N < 0):
        x = 1 / x
        N = -N

    return self.fastPow(x, N)


def fastPow(self, x, n) :
    if (n == 0) :
        return 1.0;

    half = self.fastPow(x, n // 2)
    if (n % 2 == 0) :
        return half * half
    else :
        return half * half * x<jupyter_output><empty_output><jupyter_text>Time complexity : O(log(n)). Each time we apply the formula (x ^ n) ^ 2 = x ^ {2 * n}(x​n​​ )​2​​ =x​2∗n​​ , nn is reduced by half. Thus we need at most O(log(n))O(log(n)) computations to get the result.Space complexity :O(log(n)). For each computation, we need to store the result of x ^ {n / 2}x​n/2​​ . We need to do the computation for O(log(n)) times, so the space complexity is O(log(n))O(log(n)).<jupyter_code># Iterative approch
def myPowi( x, n):
    """
    :type x: float
    :type n: int
    :rtype: float

    """
    N = n
    if (N < 0):
        x = 1 / x
        N = -N
        
    res, cur_prod, i  = 1, x, N
    while ( i > 0):
        print(i)
        if i % 2 == 1:
            res = res * cur_prod
        print("res:  {0}".format(res))    
        cur_prod = cur_prod * cur_prod
        print("cp:  {0}".format(cur_prod))   
        i = i // 2
        
    return res    
    
myPowi(2.00000, 10)
myPowi(2.10000, 3)
myPowi(2.00000, -2)<jupyter_output><empty_output><jupyter_text>Using the formula x ^ {a + b} = x ^ a * x ^ bx​a+b​​ =x​a​​ ∗x​b​​ , we can write n as a sum of positive integers, n = \sum_i b_in=∑​i​​ b​i​​ . If we can get the result of x ^ {b_i}x​b​i​​ ​​  quickly, the total time for computing x ^ nx​n​​  will be reduced.Complexity AnalysisTime complexity : O(log(n)). For each bit of n 's binary representation, we will at most multiply once. So the total time complexity is O(log(n)).Space complexity :O(1). We only need two variables for the current product and the final result of x.<jupyter_code>class Solution(object):
    def isPowerOfThree(self, n):
        if n <= 0:
        	return False

        while n % 3 == 0:        	
        	n = n / 3

        return True if n == 1 else False<jupyter_output><empty_output><jupyter_text>https://stackoverflow.com/questions/1804311/how-to-check-if-an-integer-is-a-power-of-3/2427485024274850<jupyter_code>def isPowerOfThree(self, n):
    return n > 0 == 3**19 % n<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1457572066585465, 'fraction_numerical': 0.03207470564352416, 'mean_word_length': 2.4269819193324063, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 19, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '541402', 'license': 'MIT', 'n_tokens_mistral': 1000, 'n_tokens_neox': 932, 'n_words': 290, 'path': 'Python/pow(x_n).ipynb', 'repo_name': 'AlphaTwist/Code-squad', 'size': '2463'}