Python solution with detailed explanation


  • 0
    G

    Solution

    Super Pow https://leetcode.com/problems/super-pow/

    Brute-Force Solution

    • Brute force solution uses result, iterations = int((result * int(a % 1337))%1337), iterations-1
    • Time complexity of the solution is O(b) where b is the size or value of b.
    class Solution1(object):
        def superPow(self, a, b):
            """
            :type a: int
            :type b: List[int]
            :rtype: int
            """
            factor, result = 1, 1
            for i in range(len(b)-1, -1, -1):
                iterations = b[i]*factor
                while iterations:
                    result, iterations = int((result * int(a % 1337))%1337), iterations-1
                factor *= 10
            return result
    

    Optimized Solution - Order of number of digits of b

    • The algorithm can be described using this example where b = [7,8,5]
    • a^785 = a^700 * a^80 * a^5 = ((a^70 * a^8)^10) * ( a^5)
    • (((a^7)^10 * a^8)^10) * ( a^5)
    • First iteration: a^7 and (a^7)^10 = a^70
    • Second iteration = a^70 * a^8 and (a^78)^10 = a^780
    • Third iteration = a^780 * a ^5 = a^785
    class Solution(object):
        def compute_pow(self, a, b):
            if b == 0:
                return 1
            elif b == 1:
                return a
            elif b & 1:
                x = self.compute_pow(a,(b-1)//2) % 1337
                return int(((a % 1337) * (x * x) % 1337) % 1337)
            else:
                x = self.compute_pow(a,b//2) % 1337
                return int((x * x) % 1337)
        
        def superPow(self, a, b):
            """
            :type a: int
            :type b: List[int]
            :rtype: int
            """
            a, result = a%1337, 1
            for i in range(len(b)):
                result = (result * self.compute_pow(a, b[i])) % 1337
                result = self.compute_pow(result, 10) if i != len(b)-1 else result
            return result
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.