Exceeded time limit to solve super pow I tried to solve the Super Pow - LeetCode


  
  Super Pow
  
  
  Medium
  
  Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.
  
  Example 1:

Input: a = 2, b = [3]
Output: 8

  
  Example 2:

Input: a = 2, b = [1,0]
Output: 1024



My solution 

import unittest
import logging
logging.basicConfig(level=logging.DEBUG, format="%(levelname)s %(message)s")

class Solution(object):
    def superPow(self, a, b):
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        digit = int("".join(map(str, b)))
        product = a ** digit 
        res = product % 1337
        return res

class MyCase(unittest.TestCase):
    def setUp(self):
        self.solution = Solution()

    def test_1(self):
        a = 2
        b = [1, 0]
        answer = 1024
        check = self.solution.superPow(a, b)
        self.assertEqual(answer, check)

unittest.main()


The solution exceeded the time limit.

How could I improve my solution?
Python's built-in pow already has this functionality.

class Solution(object):
    def superPow(self, a, b):
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        digit = int("".join(map(str, b)))
        return pow(a, digit, 1337)


The bottleneck then might be parsing the list of digits into the integer. To remedy that, you can try to use the fact that

\$
\begin{align}
a^{123} ~\text{mod}~ 1337 &amp;= (a^{100}\cdot a^{20}\cdot a^3)~\text{mod}~ 1337&amp; \\
              &amp;= (a^{100}~\text{mod}~ 1337 \cdot a^{20}~\text{mod}~ 1337\cdot a^3  ~\text{mod}~ 1337) ~\text{mod}~ 1337&amp; \\
\end{align}\$

class Solution(object):
    def superPow(self, a, b):
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        ret = 1
        for i, digit in enumerate(reversed(b)):
            ret = (ret * pow(a, digit * 10**i, 1337)) % 1337
        return ret




And here are some timings for inputs of increasing length (from 1 to 10 digits, because your function would take way too long otherwise), with a = 2 and where super_pow_op is your function, super_pow_built_in is my first function and super_pow_expanded is my second function.



And here for 3 to 1000 digits, but only with my two functions: