DAC solution, handle arbitrary large b. But TLE.


  • 0
    L

    I am getting TLE. Can anybody give some suggestions on how to improve this?
    I am using the divide-and-conquer approach, the running time should be logN where N is the actual decimal value of b.

    public class Solution {
    	public int superPow(int a, int[] b) {
    		int n = b.length;
    		int[] ONE = new int[n];
    		int[] ZERO = new int[n];
    		ONE[n - 1] = 1;
    		int oneHash = Arrays.hashCode(ONE);
    		int zeroHash = Arrays.hashCode(ZERO);
    		int MOD = 1337;
    
    		return superPowHelper(a % MOD, b, oneHash, zeroHash, MOD);
    	}
    
    	private int superPowHelper(int a, int[] b, int oneHash, int zeroHash, int MOD) {
    		// basecase
    		if (zeroHash == Arrays.hashCode(b)) {
    			return 1;
    		}
    
    		if (oneHash == Arrays.hashCode(b)) {
    			return a;
    		}
    
    		// divide and conquer
    		int[] dac = divide(b);
    		int dacRet = superPowHelper(a, dac, oneHash, zeroHash, MOD);
    		if ((b[b.length - 1] & 1) == 1) {
    			return (dacRet * dacRet * a) % MOD;
    		} else {
    			return (dacRet * dacRet) % MOD;
    		}
    	}
    
    	private int[] divide(int[] b) {
    		int n = b.length;
    		int[] ret = new int[n];
    
    		for (int i = n - 1; i >= 0; i--) {
    			if (i > 0 && (b[i - 1] & 1) == 1) {
    				// borrow
    				b[i - 1] -= 1;
    				b[i] += 10;
    			}
    			ret[i] = b[i] / 2;
    		}
    		return ret;
    	}
    }
    

  • 0

    Calculating the hashCode for b and comparing it will take about O(|b|) time where |b| is length of vector b.

    In this case N (actual decimal value of b) can be approximated to 10^(|b|+1) for complexity analysis purposes. Can you now see what the overall complexity is turning out to be?

    It will be close to O(|b| log(N)), which in turn reduces to something like c * O(|b|^2) where c is a constant close to log(10). That's quadratic complexity on the length of b, which will obviously timeout.


Log in to reply
 

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