Pure recursion in Java


  • 0
    S
    public class Solution {
        //ab % k = (a%k)(b%k)%k, 
        //a^n % k = ((a % k)^n) % k, proof: induction, a^10 % k = (a^9 % k) * (a % k) % k = (((a % k)^9) % k) * (a % k) % k  = ((a % k)^10) % k
        
        //(a^12345) % k = ((a^12340) * (a^5)) % k = (((a^1234)^10) * (a^5)) % k = ((((a^1234 % k)^10) % k) * ((a^5) % k)) % k
        //super(a, 12345) = powerMode((super(a,1234),10) * powerMode(a, 5) % k
        public int superPow(int a, int[] b) {
            if (b == null || b.length == 0) return 1;
            if (a == 0) return 0;
            
            return helper(a, b, b.length - 1, 1337);
        }
        
        public int helper(int a, int[] b, int index, int k) {
            if (index == 0) return powerMode(a, b[index], k);
            return (powerMode(helper(a, b, index - 1, k),10, k)*powerMode(a, b[index], k)) % k;
        }
        
        //a^b % 1337, 
        //use: ab % k = ((a%k)*(b%k))%k, 
        public int powerMode(int a ,int b, int k) {
            if (b == 0 || b == 1) return b == 0 ? 1 : a % k;
            
            return (powerMode(a, b - 1, k)*(a % k)) % k;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.