# Exceeded time limit to solve super pow

I tried to solve the Super Pow - LeetCode

1. 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]
check = self.solution.superPow(a, b)

unittest.main()


The solution exceeded the time limit.

How could I improve my solution?

• an extremely large positive integer given in the form of an array" is far too vague for a specification. Commented Apr 5, 2019 at 10:18

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:

• amazing, do you mind if I ask what' the tool you use to analyze the performance? Commented Apr 4, 2019 at 9:57
• @Alice: I used the code in my question here, plus the answer given there. Commented Apr 4, 2019 at 9:58