leetcode

commit 85842b8ae346ea399be8570a49a4626d5b2f8f45
parent dbd535bd9e0d0803402c944cd40e33229dd9a0c1
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri, 18 Oct 2024 00:18:13 -0600

372. super pow

Diffstat:
A
super_pow.c
 | 
40
++++++++++++++++++++++++++++++++++++++++
A
super_pow.py
 | 
28
++++++++++++++++++++++++++++

2 files changed, 68 insertions(+), 0 deletions(-)
diff --git a/super_pow.c 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
@@ -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]))