Super pow

Math Divide and Conquer

36.4% acceptance

Jan 12, 2026

1073

1486

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn super_pow(a: i32, b: Vec<i32>) -> i32 {
    const MOD: i32 = 1337;
    
    fn pow_mod(mut base: i32, mut exp: i32) -> i32 {
      base %= MOD;
      let mut result = 1;
      while exp > 0 {
        if exp % 2 == 1 {
          result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
      }
      result
    }
    
    let mut result = 1;
    for &digit in &b {
      result = pow_mod(result, 10);
      result = (result * pow_mod(a, digit)) % MOD;
    }
    
    result
  }
}