# DAC solution, handle arbitrary large b. But TLE.

• 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;
}
}
``````

• 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.

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