Problem

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.

Examples

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

Solution

Method 1 – Divide and Conquer Exponentiation

Intuition

The key idea is to use modular exponentiation and the property: a^(b1b2...bn) = ((a^(b1b2...bn-1))^10) * (a^bn) This allows us to break down the large exponent (given as an array) into smaller problems, recursively solving for each digit.

Approach

  1. Define a helper function to compute a^k % mod efficiently using fast exponentiation.
  2. Recursively process the exponent array from the last digit:
  • If the array is empty, return 1.
  • Pop the last digit d from the array.
  • Compute part1 = superPow(a, rest_of_b), then raise it to the 10th power modulo 1337.
  • Compute part2 = a^d % 1337.
  • Multiply part1 and part2, take modulo 1337, and return.
  1. Handle edge cases where a or b is 0 or 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
   int mod = 1337;
   int powmod(int a, int k) {
      int ans = 1;
      a %= mod;
      while (k) {
        if (k % 2) ans = ans * a % mod;
        a = a * a % mod;
        k /= 2;
      }
      return ans;
   }
   int superPow(int a, vector<int>& b) {
      if (b.empty()) return 1;
      int d = b.back(); b.pop_back();
      int part1 = powmod(superPow(a, b), 10);
      int part2 = powmod(a, d);
      return part1 * part2 % mod;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

type Solution struct{}

func (s Solution) superPow(a int, b []int) int {
   mod := 1337
   var powmod func(a, k int) int
   powmod = func(a, k int) int {
      ans := 1
      a %= mod
      for k > 0 {
        if k%2 == 1 {
           ans = ans * a % mod
        }
        a = a * a % mod
        k /= 2
      }
      return ans
   }
   if len(b) == 0 {
      return 1
   }
   d := b[len(b)-1]
   b = b[:len(b)-1]
   part1 := powmod(s.superPow(a, b), 10)
   part2 := powmod(a, d)
   return part1 * part2 % mod
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
   int mod = 1337;
   private int powmod(int a, int k) {
      int ans = 1;
      a %= mod;
      while (k > 0) {
        if (k % 2 == 1) ans = ans * a % mod;
        a = a * a % mod;
        k /= 2;
      }
      return ans;
   }
   public int superPow(int a, List<Integer> b) {
      if (b.isEmpty()) return 1;
      int d = b.remove(b.size() - 1);
      int part1 = powmod(superPow(a, b), 10);
      int part2 = powmod(a, d);
      return part1 * part2 % mod;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
   private val mod = 1337
   private fun powmod(a: Int, k: Int): Int {
      var ans = 1
      var base = a % mod
      var exp = k
      while (exp > 0) {
        if (exp % 2 == 1) ans = ans * base % mod
        base = base * base % mod
        exp /= 2
      }
      return ans
   }
   fun superPow(a: Int, b: MutableList<Int>): Int {
      if (b.isEmpty()) return 1
      val d = b.removeAt(b.size - 1)
      val part1 = powmod(superPow(a, b), 10)
      val part2 = powmod(a, d)
      return part1 * part2 % mod
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
   mod: int = 1337

   def powmod(self, a: int, k: int) -> int:
      ans = 1
      a %= self.mod
      while k:
        if k % 2:
           ans = ans * a % self.mod
        a = a * a % self.mod
        k //= 2
      return ans

   def superPow(self, a: int, b: list[int]) -> int:
      if not b:
        return 1
      d = b.pop()
      part1 = self.powmod(self.superPow(a, b), 10)
      part2 = self.powmod(a, d)
      return part1 * part2 % self.mod
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
   pub fn super_pow(a: i32, b: Vec<i32>) -> i32 {
      fn powmod(mut a: i32, mut k: i32, m: i32) -> i32 {
        let mut ans = 1;
        a %= m;
        while k > 0 {
           if k % 2 == 1 {
              ans = ans * a % m;
           }
           a = a * a % m;
           k /= 2;
        }
        ans
      }
      fn helper(a: i32, b: &[i32], m: i32) -> i32 {
        if b.is_empty() {
           return 1;
        }
        let d = b[b.len() - 1];
        let part1 = powmod(helper(a, &b[..b.len() - 1], m), 10, m);
        let part2 = powmod(a, d, m);
        part1 * part2 % m
      }
      helper(a, &b, 1337)
   }
}

Complexity

  • ⏰ Time complexity: O(n * log a) where n is the length of b.
  • 🧺 Space complexity: O(n) for recursion stack