Sunday, August 21, 2016

Super Pow

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

This is another mathematical problem. The basic idea is to use exponentiation by squaring, i.e.:

x^n = x(n/2) * x(n/2) * x if n % 2 != 0
       = x(n/2) * x(n/2) if n % 2 == 0


For the actual problem, since b is represented by array:

a^b = a^(10*len*b[len - 1] + ... + b[0]) = (a^(10 * len))^(b[len - 1])*...*(a^b[0])

Besides

(a * b) % c = ((a % c) * (b % c)) % c


public class Solution {
    private int modConstant = 1337;
    public int superPow(int a, int[] b) {
       int len = b.length;
  int rst = 1;
  for (int i = len - 1; i >= 0; i--) {
   rst = rst * quick_pow(a, b[i]) % modConstant;
   a = quick_pow(a, 10);
  }
  return rst;
    }
    
 int quick_pow(int a, int b) {
  int rst = 1;
  a %= modConstant;
  while (b > 0) {
   if (b % 2 !=0) rst = rst * a % modConstant;
   a = a * a % modConstant;
   b /= 2;
  }
  return rst;
 
    }
}

No comments:

Post a Comment