372. Super Pow

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.

Example1:

a = 2 b = [3]

Result: 8

Example2:

a = 2 b = [1,0]

Result: 1024

Credits:Special thanks to @Stomach_ache for adding this problem and creating all test cases.

Solution

public class Solution {
       private static int VALUE = 1337;

    public int superPow(int a, int[] b) {
        long result = 1;
        for (int i = 0; i < b.length; i++) {
            long first = pow(result, 10) % VALUE;
            long second = pow(a, b[i]) % VALUE;

            result = (first * second) % VALUE;
        }

        return (int) result;
    }

    private long pow(long x, int y) {
        if (y == 0) return 1;
        if (y == 1) return x % VALUE;

        x = x % VALUE;
        y = y % VALUE;
        long result = pow(x, y / 2) % VALUE;
        if (y % 2 == 1) {
            return result * result * x;
        } else {
            return result * result;
        }
    }
}