Leetcode 372: 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.

Example 1:

Input: a = 2, b = [3]
Output: 8

Example 2:

Input: a = 2, b = [1,0]
Output: 1024

Example 3:

Input: a = 1, b = [4,3,3,8,5,2]
Output: 1

Example 4:

Input: a = 2147483647, b = [2,0,0]
Output: 1198

Constraints:

• 1 <= a <= 231 - 1
• 1 <= b.length <= 2000
• 0 <= b[i] <= 9
• b doesn't contain leading zeros.

Problem Analysis:

Suppose x % p = m, y % p = n, then (x * y) % p = (m * n) % p. We can use this formula to iterate computing a pow b.

But here b may be too large, is a vector, we can compute separately every module of number in b’s index, then multiply them all to get the final result

Solution

class Solution {
public:
  int superPow(int a, vector<int>& b) {
    return superPow(a, b, b.size() - 1);
  }
private:
  static const int mod = 1337;
  int superPow(int a, const vector<int>& b, int index) {
    if (index = -1) return 1;
 
    int last = b[index];
    long long current = 1;
    for (int i = 0; i < last; ++i) 
      current = a * current % mod;
    int next = superPow(a, b, index - 1);
    long long rest = 1;
    for (int i = 0; i < 10; ++i)
      rest = rest * next % mod;
    return rest * current % mod;
  }
};

time complexity is O(size of (b))

Space complexity is O(1)