Problem statement

https://leetcode.com/problems/super-pow/

Solution

Imagine, we need to evaluate a^{5159}, it is equal to a^9 * (a^{10}) ^ {515}. So, to evaluate superPow{a, 5159}, we need to evaluate it recurrently for superPow(a**10, 515) and multiply it by a^9.

Complexity

Time complexity of this approach is O(n), where n is length of b, space complexity is also O(n). Space complexity can be reduced to O(1).

Code

class Solution:
    def superPow(self, a, b):
        def helper(a, ind):
            if ind == 0:
                return pow(a, b[ind], N)
            else:
                return (helper(pow(a, 10, N), ind-1) * pow(a, b[ind], N)) % N
    
        N = 1337
        return helper(a, len(b) - 1)