首页 > 代码库 > Leetcode: Super Pow

Leetcode: Super Pow

2024-08-23 18:56:56   219人阅读

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

a = 2
b = [3]

Result: 8
Example2:

a = 2
b = [1,0]

Result: 1024

 ab % k = (a%k)(b%k)%k
Since the power here is an array, we‘d better handle it digit by digit.
One observation:
a^1234567 % k = (a^1234560 % k) * (a^7 % k) % k = (a^123456 % k)^10 % k * (a^7 % k) % k
put it other way:
Suppose f(a, b) calculates a^b % k; Then translate above formula to using f :
f(a,1234567) = f(a, 1234560) * f(a, 7) % k = f(f(a, 123456),10) * f(a,7)%k;
Implementation of this idea:

 1 public class Solution {
 2     public int superPow(int a, int[] b) {
 3         return superPow(a, b, b.length, 1337);
 4     }
 5     
 6     public int superPow(int a, int[] b, int len, int k) {
 7         if (len == 1) return powMud(a, b[0], k);
 8         return powMud(superPow(a, b, len-1, k), 10, k) * powMud(a, b[len-1], k) % k;
 9     }
10     
11     public int powMud(int x, int y, int k) {
12         int res = 1;
13         for (int i=y; i>0; i--) {
14             x = x % k;
15             res = (res * x) % k;
16         }
17         return res;
18     }
19 }

 

Another clear solution:

 1 public class Solution {
 2     public int superPow(int a, int[] b) {
 3         int res = 1;
 4         int j = 0;
 5         a = a % 1337;
 6         while(j < b.length){
 7             int rem = pow(a,b[j]);
 8             // left shift b;
 9             res = (rem * pow(res,10)) % 1337;
10             j++;
11         }
12         return res;
13     }
14     // write a pow function to avoid overflow
15     public int pow(int a, int b){
16         int res = 1;
17         while(b > 0){
18             // module 1337 every time to avoid overflow
19             res = (res * a) % 1337;
20             b--;
21         }
22         return res;
23     }
24 }

 

Leetcode: Super Pow


联系
我们