# 1-liners & other with explanations

• ## Solution 1: Using Python's big integers (accepted in 72 ms)

Turn `b` into a Python integer object (they grow arbitrarily large) and just use the `pow` function (which supports a modulo paramenter).

``````def superPow(self, a, b):
return pow(a, int(''.join(map(str, b))), 1337)
``````

## Solution 2: Using small ints (accepted in 80 ms)

Originally I went backwards (see solution 5) but then I saw other people go forwards and it's simpler. Sigh. Anyway... my version:

``````def superPow(self, a, b):
result = 1
for digit in b:
result = pow(result, 10, 1337) * pow(a, digit, 1337) % 1337
return result
``````

Explanation: For example for a5347, the above computes a5, then a53, then a534, and then finally a5347. And a step from one to the next can be done like a5347 = (a534)10 * a7.

## Solution 3: Using recursion (accepted in 92 ms)

Obligatory recursive oneliner version of solution 2.

``````def superPow(self, a, b):
return pow(a, b.pop(), 1337) * pow(self.superPow(a, b), 10, 1337) % 1337 if b else 1
``````

## Solution 4: Using `reduce` (accepted in 80 ms)

Obligatory `reduce`-oneliner version of solution 2.

``````def superPow(self, a, b):
return reduce(lambda result, digit: pow(result, 10, 1337) * pow(a, digit, 1337) % 1337, b, 1)
``````

## Solution 5: omg was i stupid (accepted in 72 ms)

My original do-it-yourself before I saw other people's solutions and wrote solutions 2-4.

Using only small ints, also accepted in 72 ms:

``````def superPow(self, a, b):
result = 1
apower = a
for digit in reversed(b):
result = result * pow(apower, digit, 1337) % 1337
apower = pow(apower, 10, 1337)
return result
``````

Explanation by example:

a5347
= a5000 * a300 * a40 * a7
= (a1000)5 * (a100)3 * (a10)4 * a7
= (((a10)10)10)5 * ((a10)10)3 * (a10)4 * a7

Computing that from back to front is straightforward (or straightbackward?).

• In Java

``````public class Solution {
public int superPow(int a, int[] b) {
int res = 1;
int p = a;
for(int i = b.length - 1; i >=0; i--){
res = res * pow(p,b[i],1337)%1337;
p = pow(p, 10,1337);
}
return res;
}
public int pow(int a, int b, int c) {
long res = 1;
long p = a;
while (b > 0) {
if ((b & 1) == 1) {
res = (res * p) % c;
}
p = (p * p) % c;
b >>= 1;
}
return (int)(res % c);
}
}
``````

• @StefanPochmann
Time complexity?
I think it is O(N) where N is length of input array size.
Since we always keep result value < 1337, and power number always <= 10.
What do you think?

• @hpplayer Yes, should be O(n) for solutions 2-5. Just not for solution 1, as converting strings to ints looks like only O(n2):

``````>>> from timeit import timeit
>>> for e in range(10, 21):
s = '7' * 2**e
print e, timeit(lambda: int(s), number=1)

10 6.28627033657e-05
11 0.000146893459905
12 0.000254658094247
13 0.00129381706825
14 0.00357226933718
15 0.0142666263832
16 0.0555866661792
17 0.220853354784
18 0.880748810259
19 3.5156306829
20 14.1526550191
``````

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