Super Pow Problem


Description

LeetCode Problem 372.

Your task is to calculate a^b 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:

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

Example 2:

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

Example 3:

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

Example 4:

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

Constraints:

  • 1 <= a <= 2^31 - 1
  • 1 <= b.length <= 2000
  • 0 <= b[i] <= 9
  • b doesn’t contain leading zeros.


Sample C++ Code

We know that (a * b) % k = ((a % k) * (b % k)) % k.

For example, (a^1234567) % k = ((a^1234560 % k) * (a^7 % k)) % k = ((a^123456 % k)^10 % k * (a^7 % k)) % k.

Suppose f(a, b) cauclates (a ^ b) % k, then

f(a, 1234567) = f(a, 1234560) * f(a, 7) % k = f(f(a, 123456),10) * f(a,7)%k.

Since the power here is an array, we’d better handle it digit by digit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    const int base = 1337;
    int powmod(int a, int k) //a^k mod 1337 where 0 <= k <= 10
    {
        a %= base;
        int result = 1;
        for (int i = 0; i < k; ++i)
            result = (result * a) % base;
        return result;
    }
public:
    int superPow(int a, vector<int>& b) {
        if (b.empty()) return 1;
        int last_digit = b.back();
        b.pop_back();
        return powmod(superPow(a, b), 10) * powmod(a, last_digit) % base;
    }
};




Related Posts

Three Equal Parts Problem

LeetCode 927. You are given an array arr which consists...

Surface Area Of 3D Shapes Problem

LeetCode 892. You are given an n x n grid...

Super Palindromes Problem

LeetCode 906. Let’s say a positive integer is a super-palindrome...

Smallest Range I Problem

LeetCode 908. You are given an integer array nums and...

Projection Area Of 3D Shapes Problem

LeetCode 883. You are given an n x n grid...

Prime Palindrome Problem

LeetCode 866. Given an integer n, return the smallest prime...