Super Powers of 2

$\mathtt{REFERENCE :}$ This is a HacerRank problem found HERE.

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:

Also,
$(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];
  }

If we observe the solution above closely, we can observe that, to compute current value, we only need previous result. This implies that we don't need to store all previous results.

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

---

---

---