Task Description
You will be given two integers $a, b$ . You are required to output the result of $2^{2^a}$ mod $b$.Naive Solution
The naive solution would be simple compute $2^a$, then $2^{2^a}$ and finally $2^{2^a}$ mod $b$. This will work for only very small values of $a$.With the increase of the value $a$, we can't compute $2^a$ value, let alone be the final result.
Efficient Solution
Since the value $2^{2^a}$ is going to be huge for larger value of $a$, we need to find better approach to compute this.We can actually simplify the value of $2^{2^a}$ by following way:
$(a\ *\ b)\ mod\ c\ =\ [(a\ mod\ c)\ *\ (b\ mod\ c)]\ mod\ c$
$\therefore$
Recursive Solution
Based upon above relationship, we can easily solve this problem using recursion.
/**
* Compute Super Power of 2 using recursion
*/
public long compute(int a, int b) {
if (a == 0) return 2 % b;
return (compute(a - 1, b) * compute(a - 1, b)) % b;
}
Bottom Up Dynamic Programming Solution
With the recursive solution, we are going to end up computing for the same value again and again. This is will increase the time complexity. We can either apply memoization or dynamic programming to solve it efficiently.Following is the Bottom Up Dynamic Programming Solution.
/**
* Compute Super Power of 2 using dynamic programming
*/
public long compute(int a, int b) {
long[] dp = new long[a+1];
dp[0] = 2 % b;
for(int i = 1; i <= a; i++) {
dp[i] = (dp[i-1] * dp[i-1]) % b;
}
return dp[a];
}
So above solution can be further simplified as:
/**
* Compute Super Power of 2 using dynamic programming
*/
public long compute(int a, int b) {
long prev = 2 % b;
for(int i = 1; i <= a; i++) {
prev = (prev * prev) % b;
}
return prev;
}
