# Python solution with detailed explanation

• Solution

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
``````

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