diff options
-rw-r--r-- | super_pow.c | 40 | ||||
-rw-r--r-- | super_pow.py | 28 |
2 files changed, 68 insertions, 0 deletions
diff --git a/super_pow.c b/super_pow.c new file mode 100644 index 0000000..1a68436 --- /dev/null +++ b/super_pow.c @@ -0,0 +1,40 @@ +// 372. Super Pow +#include "leetcode.h" + +/* + * your task is to calculate `a^b % 1337` where 'a' is a positive integer and + * 'b' is an extremely large positive integer given in the form of an array + */ + +/* + * the number 1337 only has two divisors: 7 and 191 (excluding 1 and itself), so + * see if 'a' has a divisor of either of these. also note that 7 and 191 are + * prime numbers, meaning we can use euler's theorem, or really just fermat's + * little theorem if the mod 'n' is prime. + */ + +int power(int x, int n, int mod) { + int res = 1; + for (x %= mod; n; x *= x % mod, n >>= 1) + if (n & 1) + res *= x % mod; + return res; +} + +int superPow(int a, int *b, int bSize) { + if (!(a % 1337)) + return 0; + int n = 0; + for (int i = 0; i < bSize; i++) + n = (n * 10 + b[i]) % 1140; + if (!n) + n += 1140; + return power(a, n, 1337); +} + +int main() { + int b1[] = {3}, b2[] = {1, 0}, b3[] = {4, 3, 3, 8, 5, 2}; + printf("%d\n", superPow(2, b1, ARRAY_SIZE(b1))); // expect: 8 + printf("%d\n", superPow(2, b2, ARRAY_SIZE(b2))); // expect: 1024 + printf("%d\n", superPow(1, b3, ARRAY_SIZE(b3))); // expect: 1 +} diff --git a/super_pow.py b/super_pow.py new file mode 100644 index 0000000..1ec4c89 --- /dev/null +++ b/super_pow.py @@ -0,0 +1,28 @@ +# 372. Super Pow +from functools import reduce + +""" +your task is to calculate `a^b % 1337` where 'a' is a positive integer and +'b' is an extremely large positive integer given in the form of an array +""" + + +class Solution(object): + def superPow(self, a, b): + """ + :type a: int + :type b: List[int] + :rtype: int + """ + return ( + 0 + if a % 1337 == 0 + else pow(a, reduce(lambda x, y: (x * 10 + y) % 1140, b) + 1140, 1337) + ) + + +if __name__ == "__main__": + obj = Solution() + print(obj.superPow(a=2, b=[3])) + print(obj.superPow(a=2, b=[1, 0])) + print(obj.superPow(a=1, b=[4, 3, 3, 8, 5, 2])) |