@@ -0,0 +1,1388 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A/**%0A * Your task is to calculate a%5Eb mod 1337 where a is a positive integer and b is an extremely large positive integer%0A * given in the form of an array.%0A * %3Cp%3E%0A * Example1:%0A * %3Cp%3E%0A * a = 2%0A * b = %5B3%5D%0A * %3Cp%3E%0A * Result: 8%0A * Example2:%0A * %3Cp%3E%0A * a = 2%0A * b = %5B1,0%5D%0A * %3Cp%3E%0A * Result: 1024%0A * %3Cp%3E%0A * Tags: Math%0A * Similar Problems: (M) Pow(x, n)%0A */%0Apublic class SuperPow %7B%0A%0A%0A    public static final int BASE = 1337;%0A%0A    /**%0A     * Math.%0A     * ab %25 k = (a%25k)(b%25k)%25k.%0A     * For example, if a = 2, b = %5B1, 1%5D%0A     * 2%5E11 %25 1337 = (2%5E10 %25 1337) * (2 %25 1337) %25 1337%0A     * Then 2%5E10 can be further decomposed into (2 %25 1337)%5E10 %25 1337%0A     * https://discuss.leetcode.com/topic/50489/c-clean-and-short-solution%0A     */%0A    public int superPow(int a, int%5B%5D b) %7B%0A        return superPow(a, b, b.length);%0A    %7D%0A%0A    private int superPow(int a, int%5B%5D b, int length) %7B%0A        if (length == 0) %7B%0A            return 1;%0A        %7D%0A        int lastDigit = b%5Blength - 1%5D;%0A        length--;%0A        return powMod(superPow(a, b, length), 10) * powMod(a, lastDigit) %25 BASE;%0A    %7D%0A%0A    /**%0A     * a%5Ek %25 1337%0A     * = (a %25 1337)%5Ek %25 1337%0A     */%0A    private int powMod(int a, int k) %7B%0A        a %25= BASE;%0A        int res = 1;%0A        for (int i = 0; i %3C k; i++) %7B%0A            res = (res * a) %25 BASE; // Avoid overflow%0A        %7D%0A        return res;%0A    %7D%0A%0A%7D%0A

add Super Pow