Exceeded time limit to solve super pow

Question

I tried to solve the Super Pow - LeetCode

372. Super Pow

Medium

Your task is to calculate a^b 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?

Answer 1

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 &= (a^{100}\cdot a^{20}\cdot a^3)~\text{mod}~ 1337& \\ &= (a^{100}~\text{mod}~ 1337 \cdot a^{20}~\text{mod}~ 1337\cdot a^3 ~\text{mod}~ 1337) ~\text{mod}~ 1337& \\ \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: