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

---

---

---

Power of Powers - Minimum Number of Multiplications to compute Nth Power

Task Description

You need to find the minimum number of multiplications needed to get the desired power $n$ of a number $x$ using only previous computations.

Examples

The minimum number of multiplications required to compute $16th$ power of a number $x$ is $4$.

1. $x \times x = x^2$
2. $x^2 \times x^2 = x^4$
3. $x^4 \times x^4 = x^8$
4. $x^8 \times x^8 = x^{16}$

Similarly, the minimum number of multiplications required to compute the $15th$ power of the number is $5$.

1. $x \times x = x^2$
2. $x^2 \times x^2 = x^4$
3. $x^4 \times x = x^5$
4. $x^5 \times x^5 = x^{10}$
5. $x^5 \times x^{10} = x^{15}$

OR

1. $x \times x = x^2$
2. $x^2 \times x = x^3$
3. $x^3 \times x^3 = x^6$
4. $x^6 \times x^6 = x^{12}$
5. $x^{12} \times x^3 = x^{15}$

Solution

As can be seem from the examples, the $nth$ power of a number can be computed using previous results for power $\lt n$.

Also, as seen from the examples, there can be different combination of previous result to compute the $nth$ power. For example, we can compute $x^{15}$ using $x^5 \times x^{10}$ or using $x^{12} \times x^3$. Obviously we have multiple choices to compute this value.

Minimum Number of Multiplications

Let, $x^n = x^a \times x^b \times x^c \times x^d$ be one of the combination
Then, number of multiplication needed using this combination

$=$ number of multiplication for $x^a$ + number of multiplication for $x^b$ + number of multiplication for $x^c$ + number of multiplication for $x^d$ + 3

The last number $3$ comes from the fact that we need $3$ more multiplications to multiply $x^a,\ x^b,\ x^c\ and\ x^d$.

The required minimum number of multiplications will be the minimum of all such combinations.

Computing the Number of Multiplications for all Combinations

int min = Integer.MAX_VALUE;
for i = 2 to n/2
   // x^15, 15/2 = 7, there are 2 x^7 and we need to multiply x^7 (2-1) times
   int part1 = (i-1) + numberOfMultiplicationFor(n / i);

   // 15 % 2 = 1, 
   int part2 = numberOfMultiplicationFor(n % i)
   
   int combinationNumber =  part1 + part2;

   // if n % i != 0, we need extra 1 multiplication x^14 x x
   combinationNumber += n % i == 0 ? 0 : 1;
   
   min = Math.min(min, combinationNumber)

Special Case for Even n

For Even n, we can simply compute the number of multiplication required using,

// this will be minimum for Even n
numberOfMultiplication = numberOfMultiplicationFor(n/2) + 1;

Recursive Implementation

    if f(n) gives the minimum number of multiplication required to compute
       nth power, then

    f(n) = f(n/2) + 1 if n is even
         = Min{
                for i = 2 to n/2 
                  (i-1) + f(n/i) + f(n%i) + (1 if n%i != 0)
              }

    Base Cases:
      f(0) = f(1) = 0
      f(2) = 1
      f(3) = 2
  

Recursive implementation will give the result, but if we don't use memoization, then it will end up calculating the same value again and again. This will result into high complexity.

To improve the complexity, we can either use Memoization or Botton Up Dynamic programming. Following the Dynamic Programming solution.

Bottom Up Dynamic Programming Approach

---

---

---

Shortest Distance in X x Y x Z 3D Matrix - Efficient BFS Method

$\mathtt{REFERENCE}$ @ HackerRank

$\mathtt{RELATED\ PROBLEM}$ The problem is related to path searching in 2D matrix. Only Difference is here we are dealing with 3D matrix. Searching in 2D matrix problem can be found HERE

Task Description

Herman the worm is in his terrarium and needs help getting to a grape to eat. His terrarium is $x \times y \times z$ large and is blocked by obstacles throughout the environment.

Please write an algorithm that outputs an optimal path Herman must take to get to the grape.

$H = Herman's\ starting\ point$
$O = Open$
$X = Obstacle\ (closed)\ Herman\ can't\ travel\ this\ way.$
$G = Grape$

Input Format

The first line of input will be $x,\ y,\ z$ in the format: $x\ y\ z$
Where, $x$ is the length of the X-Axis, $y$ is the length of the Y-Axis and $z$ is the length of the Z-Axis.

This will be followed by a layout of $x, y$ map for each of $z$ layer separated by a $blank\ line$.

Constraints

$0 <= X, Y, Z <= 40$

Output Format

Output will be sequence of Motion required to reach the destionation cell G from the source Cell H in separate lines.

Sample Inputs and Outputs

Sample Input 0

2 3 2

HX
OX
OX

XG
XO
OO

Sample Output 0

Y+
Y+
Z+
X+
Y-
Y-

Sample Input 1

3 3 2

HXG
OXX
OXX

XXO
XXO
OOO

Sample Output 1

Y+
Y+
Z+
X+
X+
Y-
Y-
Z-

Sample Input 2

4 4 4

GOOO
OOXO
OOOO
OOOO

OXXX
XXHX
XXXX
XXXX

OXXX
XXOX
XXXX
XXXX

OXXO
OOOO
OOOO
OOOO

Sample Output 2

Z+
Z+
X-
X-
Y-
Z-
Z-
Z-

The target is to find the shortest path distance from the source to the destination location. You can move to only $left,\ right,\ up\ or\ down cells$.

Solution: BFS Method - Efficient Method

Similar to the path searching Problem in 2D Matrix, this problem can also be solved efficiently using Breadth First Search (BFS) method. Using BFS method, we will be exploring any cell only once. $\therefore$ The Time Complexity of this method will be $\cal{O(xyz)}$.

Implementation

---

---

---

Shortest Distance in m x n Matrix from Source to Destination

$\mathtt{RELATED\ PROBLEM}$ Path Searching in 3D Matrix

Task Description

Given a $m \times n$ matrix filled with 0's as permissible path. There is $only\ one\ source\ location$ indicated by a character '$*$'. There are $zero\ or\ more\ location$ where there is a food (or Destination) indicated by '$\#$' character.

The target is to find the shortest path distance from the source to the destination location. You can move to only $left,\ right,\ up\ or\ down cells$.

Solution 1: Brute Force / Recursive Solution

The brute force method is to try out all the paths possible and find the minimum path out of all those.

To find all the possible paths, we need to use recursive method. Since we are computing all the possible paths and there can be exponentially many paths, this method is going to be very very slow for larger input matrix.

Implementation

Time Complexity

There are exponentially many paths possible from source to destination. Since we are considering all those paths, the time complexity is also Exponential which becomes very slow with increase in input size.

Solution 2: BFS Method - Efficient Method

This problem can be solved efficiently using Breadth First Search (BFS) method. Using BFS method, we will be exploring any cell only once. $\therefore$ The Time Complexity of this method will be ${\cal O}(mn)$.

Implementation

---

---

---

HackerRank Problem: Birthday Chocolate

This is a HackerRank Problem. You can find it HERE

This is actually a very easy problem. I have decided to write a blog on it to remind myself of a mistake that I did when solving this.

Task Description

Lily has a chocolate bar that she wants to share it with Ron for his birthday. Each of the squares has an integer on it. She decides to share a contiguous segment of the bar selected such that the length of the segment mathches Ron's birth month and the sum of the integers on the squares is equal to his birth day. You must determine how many ways she can divide the chocolate.

Consider the chocolate bar as an array of squares, $s = [2, 2, 1, 3, 2]$. She wants to find segments summing to Ron's birth day, $d = 4$ with a length equalling his birth month, $m = 2$. In this case, there are two segments meeting her criteria: $[2, 2]\ and\ [1, 3]$.

Assumption

Chocolate bar has at least the length of 1. $i.e.$ The input $array\ length >= 1$.

Initial Solution (Fails For an Edge Case)

  static int solve(int n, int[] s, int d, int m) {
    int i = 0, j = 1;
    int sum = s[i];
    int counts = 0;
    for(; j < s.length; j++) {
        sum += s[j];
        
        if (sum > d) {
            sum -= s[i];
            i++;
        } else if (j - i == m - 1) {
            if (sum == d) counts++;
            sum -= s[i];
            i++;
        }
    }
    return counts;
  }

Simple isn't it? But it fails for an EDGE case. Can guess the Edge Case?

The Edge Case

Well the edge case is, in the code we have initialized sum as the first element of the array and as soon as we enter the loop we increment the sum with the second element of the array. This means we never consider the case where $m == 1$.

Actual Solution

We can solve this by initially considering NO any elements. We will start considering elements only after we start loop. So the only changes to be made are

int j = 0; // instead of j = 1;

and,
int sum = 0; // instead of sum = s[i]

  static int solve(int n, int[] s, int d, int m) {
    int i = 0, j = 0;
    int sum = 0;
    int counts = 0;
    for(; j < s.length; j++) {
        sum += s[j];
        
        if (sum > d) {
            sum -= s[i];
            i++;
        } else if (j - i == m - 1) {
            if (sum == d) counts++;
            sum -= s[i];
            i++;
        }
    }
    return counts;

}

Complexity

The solution solves the problem in one pass without using extra memory. So the time complexity is $\cal{O(n)}$ and the space complexity is $\cal{O(1)}$.

---

---

---

Shuffling Algorithm - Knuth Algorithm

You must be familiar how we shuffle a deck of card before start of any game. Its easy in real life to shuffle the deck of cards with hand.

How about in the online games? How would we shuffle a deck of card?

Shuffling should be done such that all the cards must be distributed uniformly i.e. every card should be distributed across the positions with equal probability. For the case of n items, all the items should be distributed with the probability of ${1 \over N}$.

Algorithm

1. We start by initializing $position = 0$.
2. Randomly pick an item from the array, range of the selection being $[position, N]$, where N = size of the array.
3. Swap the position of this random item with the item in the location $position$.
4. Increase $position$ by 1 and repeat from step 2 until $position == N$

Following this algorithm, it can be guaranteed that that each of the items in the array is uniformly distributed across the array with the probability of ${1 \over n}$.

$\def\specialFrac#1#2{\frac{x + #1}{y + #2}}$
• Probability of first item = $1 \over N$
• Probability of second item = \(\textrm{probability of not being selected for first time} \times \textrm{probability of getting selected out of (N-1) items}\) = $\frac {N-1}{N} \times \frac {1}{N-1}$ = $\frac {1}{N}$
• Probability of third item = \(\textrm{probability of not being selected for first time} \times \textrm{probability of not being selected for second time} \times \) \(\textrm{probability of getting selected out of (N-2) items}\) = $\frac {N-1}{N} \times \frac {N-2}{N-1} \times \frac {1}{N-2}$ = $\frac {1}{N}$
• and so on...

So we can see that the probability of \(\frac{1}{N}\) can be guaranteed for each of the items in the arra.

Implementation

Complexity

The algorithm shuffles the array in one pass and in place. So, the overall time complexity is $\cal{O(n)}$ and space complexity is $\cal{O(1)}$.

---

---

---

java.sql.SQLException: Operation not allowed after ResultSet closed

I faced this problem recently. As a part of closing some resources, I was closing resources in the finally block.

  ResultSet resultSet; // class variable

  ...
  ...
  Statement st = null;
  try {
    st = conn.createStatement();
    resultSet = st.getGeneratedKeys();
  } catch (Exception e) {
    throw e;
  } finally {
    try {
      if (st != null) st.close();
    } catch (SQLException e) {
      throw e;
    }
  }

      

As soon as I did this, I started to get the exception when I tried resultSet.hasNext();

java.sql.SQLException: Operation not allowed after ResultSet closed

My initial guess was I might have executed resultSet.close() somewhere. But it was not the case.

Problem

The actual problem is, ResultSet instance also saves underlying Statement. So, when the underlying Statment is closed (as done in the FINALLY block above), ResultSet is also closed. This causes the problem.

JavaDoc has clearly mentioned this.

When a Statement object is closed, its current ResultSet object, if one exists, is also closed.

Solution

So to fix the problem, you obviously cannot close the Statement instance untill you are done with ResultSet. Once you are done with ResultSet, you can close both ResultSet and Statement.

---

---

---

Count Number of Words in the given input String

Task Description

Given an input string, you need to get the number of words or list of words delimited by prefefined list of delimiter characters.

Simple Solution (Incorrect Solution)

I had come across this problem for the first time when I had just joined by Undergraduate Program. Then I was just learning how to code. So when I was given this problem for the first time, the solution I came up with was to traverse the entire string and count the number of delimiters. It would give correct word count for a normal sentence where we would expect only one delimiter in between each word and no leading or trailing spaces in the string.

Correct Solution

Idea

The problem in the simple solution discussed above is that there could be contigous sequence of delimiters in between the words. So the idea is to increase the word count only when we encounter a Non-Delimiter character right after a Delimiter character.

Edge Case

The edge case in this solution is, if there are no delimiters in the beginning of the string, then we will be missing the first word because we are increasing word count only after we encounter a delimiter character. This can be easily solved by assuming that we have encountered delimiters in the beginning.

Psuedo-Code

  boolean delimiter = true // assume we  have already encountered delimiters in the beginning to consider first word if there are leading delimiters
  int count = 0
  for i = 0 to input.length - 1
    char current = input.charAt(i)
    if current == delimiter:
      delimiter = true
    else 
      if delimiter: // non delimiter found after delimiters, increase word count
        count++
      delimiter = false

  return count

      

Similar logic can applied to actually get the list of words in the input string.

Implementation

Following the complete implemenation for the task. The method count() returns the number of words in the string and getWords() returns the list of the words.

The implementation has also pre-defined a list of delimiters based on which the input string will be splitted into words. Delimiters can be added or removed.

Complexity

We are traversing the string only once. For each character, we check if it is delimiter or not by comparing with a HashSet - this operation is contant time ${\cal O}(1)$ operation. Then we just set a boolean value and increase count if needed. Both of these are also constant time operations. $\therefore$ the overall time complexity of this solution is ${\cal O}(n)$, n being the length of the input string. Space complexity of the solution is obviously ${\cal O}(1)$.

---

---

---

Detect Loop in Linked List And Identify the Start of Loop

Task Description

Detect if a given linked list has a loop. If it has a loop, find the starting node of the loop.

Solution 1 : Simple Solution

When I first came across this problem, the solution that I thought of was to traverse through all the nodes and for every node, check if we have already encountered this node. If we ecnounter a node which has already been visited before, then the linked list has a loop. We can efficiently check if the node has already been visited by maitaining a HashSet of already visited nodes. The starting node of the loop will the first repeated node encountered.

If the linked list does not have a loop, then the traversal of the list will terminate without encountering any repeated node.

Implementation

Complexity

In this method, we traverse through all the nodes only once except the first repeated node if it exists. The repeated node will be traversed twice. Checking for a repeated node using HashSet is a constant time operation. $\therefore$ The Time Complexity of this method is ${\cal O}(n)$ time.

But we are saving each traversed node into a HashSet. $\therefore$ The Space Complexity of this method is also ${\cal O}(n)$ time.

Solution 2: Efficient Solution (Floyd's Method)

Floyd gave a more efficient method than discussed above. This method is efficient in terms of the space used. Time Complexity remains ${\cal O}(n)$ while the Space Complexity is constant time ${\cal O}(1)$.

Principle

Floyd's method is based upon a principle that if two pointers - one moving at the speed of one node at a time and another at twice the speed of the first, are circulating in a loop, then they will always meet at a node.

At any time, if Faster Pointer is just behind the Slower Pointer, then in the next step, they will meet.

At any time, if the Faster Pointer is just aheadd of the Slower Pointer, this position is possible only if they have met in the previous step.

Detecting the Loop

Mathematics - Identify the Start of Loop

Let, when the two pointers intersect,

$\ \ \ \ \ \ m = length\ of\ the\ non-loop\ branch$
$\ \ \ \ \ \ n = length\ of\ the\ loop$
$\ \ \ \ \ \ k = length\ from\ starting\ point\ of\ the\ loop\ to\ the\ point\ of\ intersection$

$\ \ \ \ \ \ x = number\ of\ complete\ loops\ made\ by\ the\ slower\ pointer$
$\ \ \ \ \ \ y = number\ of\ complete\ loops\ made\ by\ the\ faster\ pointer$

Now,
$\ \ \ \ \ \ distance\ traveled\ by\ faster\ pointer\ (F) = m + k + yn$
$\ \ \ \ \ \ distance\ traveled\ by\ slower\ pointer\ (S) = m + k + xn$

Since, faster pointer has moving at double the speed of slower pointer,
$\ \ \ \ \ \ \ \ \ F = 2S$
$\ \ \ \ \ \ => m + k + yn = 2(m + k + xn)$
$\ \ \ \ \ \ => m + k + yn = 2(m + k) + 2xn$
$\ \ \ \ \ \ => m + k = yn - 2xn$
$\ \ \ \ \ \ => m + k = n(y - 2x)$
$\ \ \ \ \ \ => \because faster\ pointer\ is\ moving\ at\ double\ speed,\ (y - 2x) >= 1\ and\ is\ ALWAYS\ an\ Integer.$
$\ \ \ \ \ \ => m + k = certain\ number\ of\ COMPLETE\ loop\ cycles$

So, we can conclude that,

1. If Two Pointers (move at the same speed) start moving at the same time, one start from beginning of the linked list and another start from beginning of the loop, by the time the first Pointer travels $m + k$ nodes, the second Pointer will make certain number of complete loop and reach the beginning the loop again.
2. If the first pointer moves only $m$ nodes, then the second pointer will complete some loop and travel $n- k$ nodes.
3. If the second pointer starts from the point of intersection instead of beginning of the loop, both of the pointer will meet at the beginning of the loop. This is our REQUIRED start of the loop.

Compute Start of the Loop

So based upon the theory above, we can find the start of the loop by following way:

1. When the two pointers meet (the loop is detected), keep one pointer at the same location and move the other to the beginning of the linked list.
2. Now move the two pointers at the same speed - one node at a time.
3. When the two pointers meet, the meeting point will be the beginning of the loop.

Complete Implementation

Time Complexity

Time complexity is ${\cal O}(n)$ and the Space complexity is ${\cal O}(1)$.

---

---

---

PowerMockito - Mocking One Static Method and Not Mocking Other in the Same Class

Suppose we have a class,

  public class ClassWithPrivateStaticMethods {
  
   private static String getParam(String paramName) {
      String result = "";

      ...
      ...

      return result;
   }

   private static String getDetail(String contextName) {
      String result = "";

      String temp = getParam(tempParamName);
      ...

      return result;
   }
}

Until today, to mock static method, I had been doing:

  PowerMockito.mockStatic(ClassWithPrivateStaticMethods.class);
  PowerMockito.when(ClassWithPrivateStaticMethods.class, "getParam", Mockito.anyString()).thenReturn("dummy");

This works only when your test executes only this static method getParam().

Problem

PowerMockito.mockStatic() actually mocks all the static method in the class.

So if you have the circumstance where you want to mock one static method, but you want other method to run normally, then this method will not work. Because the other method will also be mocked.

  PowerMockito.mockStatic(ClassWithPrivateStaticMethods.class)
  PowerMockito.when(ClassWithPrivateStaticMethods.class, "getParam", Mockito.anyString()).thenReturn("dummy");
  String result = Whitebox.invokeMethod(ClassWithPrivateStaticMethods.class, "getDetail", Mockito.anyString());

here result will not the result of the execution of the method getDetail() but result of mocked up which is either null or equivalent because we haven't defined mock for the method getDetail

Solution - Partial Mocking

We can solve this by mocking individual static methods by following way:

  PowerMockito.spy(ClassWithPrivateStaticMethods.class);
  PowerMockito.doReturn("dummy").when(ClassWithPrivateStaticMethods.class, "getParam", Mockito.anyString())
  String finalResult = Whitebox.invokeMethod(ClassWithPrivateStaticMethods.class, "getDetail", Mockito.anyString());

Complete Code Demonstration

Following is a complete code demonstration.

---

---

---