1
\$\begingroup\$

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]
        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?

\$\endgroup\$
  • \$\begingroup\$ an extremely large positive integer given in the form of an array" is far too vague for a specification. \$\endgroup\$ – Peter Taylor Apr 5 at 10:18
2
\$\begingroup\$

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.

enter image description here

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

enter image description here

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.