372. Super Pow

// LeetCode URL: https://leetcode.com/problems/super-pow/
/**
 * a ^ (5236) = ( ( (a^5)^10 * a^2)^10 * a^3)^10 * a^6
 *
 * (a*b) % k = ( (a%k) * (b%k) ) % k
 *
 * Time Complexity: O(N * 2 * log 10) = O(N). getPow is recursivly called
 * maximum 4 times.
 *
 * Space Complexity: O(log 10) = O(1). getPow recursion stack will maximum be of
 * size 4. As each number in array b is a single digit.
 */
class Solution {

    int DIV = 1337;

    public int superPow(int a, int[] b) {
        a = a % DIV;
        if (a == 0 || b == null) {
            return 0;
        }
        if (a == 1 || b.length == 0) {
            return a;
        }

        int result = 1;

        for (int i = 0; i < b.length; i++) {
            result = getPow(result, 10) * getPow(a, b[i]) % DIV;
        }

        return result;
    }

    private int getPow(int a, int b) {
        if (a == 1 || b == 0) {
            return 1;
        }
        if (a == 0 || b == 1) {
            return a;
        }

        int res = getPow(a * a % DIV, b / 2);

        return b % 2 == 0 ? res : a * res % DIV;
    }
}