Fast Power - Lintcode Java | Welkin Lan

Fast Power – Lintcode Java | Welkin Lan
http://www.jiuzhang.com/solutions/fast-power/
Calculate the aⁿ % b where a, b and n are all 32bit integers inO(logn).

Math problem, have to know the equivalences of modulo %

• 
• \
• 

    public int fastPower(int a, int b, int n) {

        // write your code here

        if (n == 1) {

            return a % b;

        }

        if (n == 0) {

            return 1 % b;

        }

        long half = fastPower(a, b, n / 2);

        long result = (half * half) % b;

        if (n % 2 == 1) {

            result = (result * a) % b;

        }

        return (int) result;

    }

http://codingforspeed.com/using-faster-integer-power-in-java/
Read full article from Fast Power – Lintcode Java | Welkin Lan