LC-0372 Medium LeetCode

372. Super Pow

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 35% Topics: Math, Divide and Conquer

Reading material

Math & Geometry 12 min Divide & Conquer 11 min

Reference solution (spoiler · python)

# Time:  O(n), n is the size of b.
# Space: O(1)

class Solution(object):
    def superPow(self, a, b):
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        def myPow(a, n, b):
            result = 1
            x = a % b
            while n:
                if n & 1:
                    result = result * x % b
                n >>= 1
                x = x * x % b
            return result % b

        result = 1
        for digit in b:
            result = myPow(result, 10, 1337) * myPow(a, digit, 1337) % 1337
        return result

Solution from kamyu104/LeetCode-Solutions · MIT