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.

Rust Solution

struct Solution;

impl Solution {
    fn super_pow(a: i32, mut b: Vec<i32>) -> i32 {
        let a = a % 1337;
        if let Some(last) = b.pop() {
            Self::pow_mod(Self::super_pow(a, b) % 1337, 10) * Self::pow_mod(a, last) % 1337
        } else {
            1
        }
    }

    fn pow_mod(a: i32, k: i32) -> i32 {
        let mut res = 1;
        for _ in 0..k {
            res *= a;
            res %= 1337;
        }
        res
    }
}

#[test]
fn test() {
    let a = 2;
    let b = vec![3];
    let res = 8;
    assert_eq!(Solution::super_pow(a, b), res);
    let a = 2;
    let b = vec![1, 0];
    let res = 1024;
    assert_eq!(Solution::super_pow(a, b), res);
}

Having problems with this solution? Click here to submit an issue on github.