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

	/* File: PowerOfPowers.java
	* Created: 2018-05-26
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	import java.io.*;
	import java.util.*;
	/**
	* Computes minimum number of multiplication required to compute the nth power of a number
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class PowerOfPowers {
	/**
	* Driver method
	*/
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	System.out.println("Enter the value of n:" + compute(sc.nextInt()));
	} // main
	//---------------------------------------------------------------------------
	/**
	* Computes the minimum number of mulitplication
	* using bottom dynamic programming
	* @param
	*/
	public static int compute(int n) {
	int[] dp = new int[n + 1];
	for (int i = 0; i <= n; i++) {
	dp[i] = helper(i, dp);
	}
	return dp[x];
	} // compute
	//---------------------------------------------------------------------------
	/**
	* helper method that computes miniumum number of multplications
	* required to compute nth power of a number. It uses previous
	* results to compute the value
	*
	* @param n nth power to compute
	* @param dp previous results
	*/
	public static int helper(int n, int[] dp) {
	int[] baseCases = new int[]{0, 0, 1, 2, 2};
	if (n <= 3) return baseCases[n];
	int min = Integer.MAX_VALUE;
	if (n % 2 == 0) return dp[n / 2] + 1; // even n
	for (int i = 2; i <= n / 2; i++) {
	int part1 = (i - 1) + dp[n / i];
	int part2 = dp[n % i];
	int result = part1 + part2 + (n % i == 0 ? 0 : 1);
	min = Math.min(result, min);
	}
	return min;
	} // helper
	} // PowerOfPowers

view raw PowerOfPowers.java hosted with ❤ by GitHub

---

---

---

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

	/* File: HermanWorm.java
	* Created: 5/24/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.Scanner;
	/**
	* Finds the shortest distance from source to destination in
	* 3D array
	*
	* @author Sabbir Manandhar
	* manandhar.sabbir@gmail.com
	* @version 1.0
	*/
	public class HermanWorm {
	private static int X, Y, Z;
	/**
	* Driver Method
	* Reads Input from console as explained in the post
	*
	* @param args
	* @throws Exception
	*/
	public static void main(String[] args) throws Exception {
	Scanner sc = new Scanner(System.in);
	X = sc.nextInt();
	Y = sc.nextInt();
	Z = sc.nextInt();
	//System.out.println(X + " " + Y + " " + Z);
	sc.nextLine();
	sc.nextLine();
	Cell[][][] maze = new Cell[X][Y][Z];
	int sx = -1, sy = -1, sz = -1;
	for (int z = 0; z < Z; z++) {
	for (int y = 0; y < Y; y++) {
	String line = sc.nextLine();
	//System.out.println(line);
	if (line.length() != X) throw new Exception("Error reading input");
	for (int x = 0; x < X; x++) {
	char c = line.charAt(x);
	if(c == 'H') {
	sx = x;
	sy = y;
	sz = z;
	}
	maze[x][y][z] = new Cell(c, new int[]{x, y, z});
	}
	}
	if (sc.hasNextLine()) sc.nextLine();
	}
	//System.out.println(sx + " " + sy + " " + sz);
	solve(maze, sx, sy, sz);
	} // main
	//-----------------------------------------------------------------------------------------------
	/**
	* Searches for the Destination cell in a BFS fashion
	*
	* @param matrix 3D matrix where we need to find the destination cell from source
	* @param x source x location
	* @param y source y location
	* @param z source z location
	* @throws Exception
	*/
	public static void solve(Cell[][][] matrix, int x, int y, int z) throws Exception {
	// delta values to find neighboring cells of current cell
	int[][] delta = new int[][]{{-1, 0, 0}, // negative X
	{1, 0, 0}, // positive X
	{0, -1, 0}, // negative Y
	{0, 1, 0}, // positive Y
	{0, 0, -1}, // negative Z
	{0, 0, 1}}; // positive Z
	Queue<Cell> queue = new LinkedList<Cell>();
	Cell source = matrix[x][y][z];
	queue.offer(source);
	while (!queue.isEmpty()) {
	Cell parent = queue.poll();
	for (int i = 0; i < delta.length; i++) {
	// location of neighbor cell
	int nx = parent.getLocation()[0] + delta[i][0];
	int ny = parent.getLocation()[1] + delta[i][1];
	int nz = parent.getLocation()[2] + delta[i][2];
	if (isValidLocation(nx, ny, nz)) {
	Cell neighbor = matrix[nx][ny][nz];
	if (!neighbor.isVisited() && !neighbor.isObstacle()) {
	neighbor.setParent(parent);
	neighbor.setVisited();
	//System.out.println(neighbor);
	neighbor.setMotion(getMotion(parent, neighbor));
	if (neighbor.isDestination()) {
	printResult(neighbor);
	return;
	} else {
	queue.offer(neighbor);
	}
	}
	}
	}
	}
	} // solve
	//---------------------------------------------------------------------------------------------------
	/**
	* Motion required to move from Source cell to Destination Cell
	* @param source Source Cell
	* @param destination Destination Cell
	* @return X+ if the motion needed is positive unit distance in X direction
	* X- if the motion needed is negative unit distance in X direction
	* Y+ if the motion needed is positive unit distance in Y direction
	* Y- if the motion needed is negative unit distance in Y direction
	* Z+ if the motion needed is positive unit distance in Z direction
	* Z- if the motion needed is negative unit distance in Z direction
	* @throws Exception
	*/
	private static String getMotion(Cell source, Cell destination) throws Exception {
	int dx = destination.getLocation()[0] - source.getLocation()[0];
	int dy = destination.getLocation()[1] - source.getLocation()[1];
	int dz = destination.getLocation()[2] - source.getLocation()[2];
	if (dx == 1 && dy == 0 && dz == 0) return "X+";
	if (dx == -1 && dy == 0 && dz == 0) return "X-";
	if (dy == 1 && dx == 0 && dz == 0) return "Y+";
	if (dy == -1 && dx == 0 && dz == 0) return "Y-";
	if (dz == 1 && dy == 0 && dx == 0) return "Z+";
	if (dz == -1 && dy == 0 && dx == 0) return "Z-";
	throw new Exception("getMotion: Something is wrong");
	} // getMotion
	//--------------------------------------------------------------------------------------------------
	/**
	* Print the result once the destination cell is found
	* This is Recursive implementation
	* @param dest Destination Cell
	*/
	private static void printResult(Cell dest) {
	if (dest.isSource()) {
	return;
	}
	printResult(dest.getParent());
	System.out.println(dest.getMotion());
	} // printResult
	//--------------------------------------------------------------------------------------------------
	/**
	* Determine is the location represented by inputs is a valid location in the
	* given input matrix
	* @param x x location
	* @param y y location
	* @param z z location
	* @return True if the location is within the matrix else False
	*/
	public static boolean isValidLocation(int x, int y, int z) {
	return !(x < 0 || x >= X || y < 0 || y >= Y || z < 0 || z >= Z);
	} // isValidLocation
	//---------------------------------------------------------------------------------------------------
	} // HermanWorm
	//====================================================================================================
	/**
	* Class representing a Cell in a Matrix
	*/
	class Cell {
	private int[] location;
	private char c;
	private boolean visited;
	private Cell parent;
	private String motion;
	/**
	* Constructor
	* @param c character in the cell
	* @param location [x,y,z] location triplet
	*/
	public Cell(char c, int[] location) {
	this.c = c;
	this.location = location;
	this.visited = false;
	this.parent = null;
	} // Cell
	//-------------------------------------------------------------------------------------------------
	/**
	* Sets the cell as visited
	*/
	public void setVisited() {
	visited = true;
	} // setVisited
	//-------------------------------------------------------------------------------------------------
	/**
	* Sets parent of the cell during the search to a destination via shortest path
	* Parent is the parent of this cell in the path
	* @param parent
	*/
	public void setParent(Cell parent) {
	this.parent = parent;
	} // setParent
	//-------------------------------------------------------------------------------------------------
	/**
	* Determine whether the cell is visited
	* @return true if the cell is visited, else false
	*/
	public boolean isVisited() {
	return this.visited;
	} // isVisited
	//-------------------------------------------------------------------------------------------------
	/**
	* Get parent of this cell in the path, if already set
	* @return the parent cell if it has been set, else it will be null
	*/
	public Cell getParent() {
	return this.parent;
	} // getParent
	//-------------------------------------------------------------------------------------------------
	/**
	* Determine if this cell is a destination cell
	* @return True if this cell is a destination cell, else false
	*/
	public boolean isDestination() {
	return this.c == 'G';
	} // isDestination
	//-------------------------------------------------------------------------------------------------
	/**
	* Determine if this cell is an obstacle
	* @return True if this cell is an obstacle, false otherwise
	*/
	public boolean isObstacle() {
	return this.c == 'X';
	} // isObstacle
	//-------------------------------------------------------------------------------------------------
	/**
	* Determine if this cell is a source
	* @return True if this cell is source, false otherwise
	*/
	public boolean isSource() {
	return this.c == 'H';
	} // isSource
	//-------------------------------------------------------------------------------------------------
	/**
	* Get the motion which is required to reach this cell from the parent cell in the shortest path
	* @return the motion X+/X-/Y+/Y-/Z+/Z-
	*/
	public String getMotion() {
	return this.motion;
	} // getMotion
	//-------------------------------------------------------------------------------------------------
	/**
	* Sest the motion to reach this cell from the parent cell
	* @param motion the motion X+/X-/Y+/Y-/Z+/Z-
	*/
	public void setMotion(String motion) {
	this.motion = motion;
	} // setMotion
	//-------------------------------------------------------------------------------------------------
	/**
	* get the x, y, z location triplet of this cell in the input matrix
	* @return
	*/
	public int[] getLocation() {
	return this.location;
	} // getLocation
	//-------------------------------------------------------------------------------------------------
	/**
	* String representation of this cell
	* Written for debug pupose
	* @return
	*/
	public String toString() {
	return this.c + " " + this.visited + " " + (this.parent != null ? this.parent.c : null);
	} // toString
	//-------------------------------------------------------------------------------------------------
	}

view raw HermanWorm.java hosted with ❤ by GitHub

---

---

---

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

	/* File: MatrixShortestDistanceRecursive.java
	* Created: 2017-06-28
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2017 Hogwarts.
	*/
	/**
	* Given a MxN matrix. Filled with 0's
	* There is one source location indicated by character '*'
	* There are one or more location where there is a Food. Indicated by '#'
	* Find the Shortest distance to any one of the Food location.
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class MatrixShortestDistanceRecursive {
	static boolean pathFound = false;
	/**
	* driver method
	* @param args
	*/
	public static void main(String[] args) {
	MatrixShortestDistanceRecursive sln = new MatrixShortestDistanceRecursive();
	char[][] input = new char[][]{
	{'*','X','#','X','#'},
	{'0','0','X','X','0'},
	{'0','0','0','X','0'},
	{'0','0','0','0','0'},
	{'0','0','0','0','0'}
	};
	System.out.println(sln.getFood(input));
	} // main
	// ---------------------------------------------------------------------------------------------------
	/**
	* Find shortest distance to food location
	* @param grid input matrix
	* @return shortest distance
	*/
	public static int getFood(char[][] grid) {
	boolean sourceFound = false;
	int sourceR = 0, sourceC = 0; // Source Location
	// find source location
	for(int r = 0; r < grid.length; r++) {
	for(int c = 0; c < grid[0].length; c++) {
	if (grid[r][c] == '*') {
	sourceR = r;
	sourceC = c;
	sourceFound = true;
	break;
	}
	}
	if (sourceFound) break;
	} // end for find source location
	boolean[][] processed = new boolean[grid.length][grid[0].length];
	processed[sourceR][sourceC] = true;
	int len = expolorePath(grid, processed, sourceR, sourceC, 0, Integer.MAX_VALUE);
	return pathFound ? len : -1;
	} // getFood
	// ---------------------------------------------------------------------------------------------------
	/**
	* Recursive method.
	* explore path to destination food location from given location
	* @param grid input matrix
	* @param processed matrix indicating specifica locations have been processed
	* @param r current row
	* @param c current column
	* @param pathSize current pathSize at location r,c
	* @param shortestSoFar shortest path discovered so far
	* @return shortest path found
	*/
	public static int expolorePath(char[][] grid, boolean[][] processed, int r, int c, int pathSize, int shortestSoFar) {
	if (grid[r][c] == '#') {
	pathFound = true;
	return pathSize;
	}
	int[] deltaR = {-1, 0, 1, 0};
	int[] deltaC = {0, 1, 0, -1};
	for(int i = 0; i <= 3; i++) {
	int neighborR = r + deltaR[i];
	int neighborC = c + deltaC[i];
	if (isPermitted(grid, neighborR, neighborC) && !processed[neighborR][neighborC]) {
	processed[neighborR][neighborC] = true;
	int len = expolorePath(grid, processed, neighborR, neighborC, pathSize+1, shortestSoFar);
	if ( len > -1) {
	shortestSoFar = Math.min(shortestSoFar, len);
	}
	processed[neighborR][neighborC] = false;
	}
	}
	return pathFound ? shortestSoFar : -1;
	} // expolorePath
	// ---------------------------------------------------------------------------------------------------
	/**
	* determine if a given location is permissible to move or not
	* @param grid input matrix
	* @param r given location's row
	* @param c given location's column
	* @return boolean whether the location is permitted or not
	*/
	public static boolean isPermitted(char[][] grid, int r, int c) {
	if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length) {
	return grid[r][c] != 'X';
	}
	return false;
	} // isPermitted
	// ---------------------------------------------------------------------------------------------------
	}

view raw MatrixShortestDistanceRecursive.java hosted with ❤ by GitHub

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

	/* File: MatrixShortestDistanceBFS.java
	* Created: 2017-06-28
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2017 Hogwarts.
	*/
	import java.util.LinkedList;
	import java.util.Queue;
	/**
	* Given a MxN matrix. Filled with 0's
	* There is one source location indicated by character '*'
	* There are one or more location where there is a Food. Indicated by '#'
	* Find the Shortest distance to any one of the Food location.
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class MatrixShortestDistanceBFS {
	/**
	* driver method
	* @param args
	*/
	public static void main(String[] args) {
	MatrixShortestDistanceRecursiveBFS sln = new MatrixShortestDistanceRecursiveBFS();
	char[][] input = new char[][]{
	{'0','X','#','X','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0'},
	{'0','0','X','X','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','*','X','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','X',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','X','#',},
	};
	/*char[][] input = new char[][]{
	{'*','X','#','X','#'},
	{'0','0','X','X','0'},
	{'0','0','0','X','0'},
	{'0','0','0','0','0'},
	{'0','0','0','0','0'}
	};*/
	System.out.println(sln.getFood(input));
	} // main
	// ---------------------------------------------------------------------------------------------------
	/**
	* Find shortest distance to food location
	* @param grid input matrix
	* @return shortest distance
	*/
	public static int getFood(char[][] grid) {
	boolean sourceFound = false;
	int sourceR = 0, sourceC = 0; // Source Location
	// find source location
	for(int r = 0; r < grid.length; r++) {
	for(int c = 0; c < grid[0].length; c++) {
	if (grid[r][c] == '*') {
	sourceR = r;
	sourceC = c;
	sourceFound = true;
	break;
	}
	}
	if (sourceFound) break;
	} // end for find source location
	boolean[][] processed = new boolean[grid.length][grid[0].length];
	processed[sourceR][sourceC] = true;
	int[][] pathLenths = new int[grid.length][grid[0].length];
	return explorePath(grid, processed, pathLenths, sourceR, sourceC);
	} // getFood
	// ---------------------------------------------------------------------------------------------------
	/**
	* BFS method.
	* explore path to destination food location from given location
	* @param grid input matrix
	* @param processed matrix indicating specifica locations have been processed
	* @param r current row
	* @param c current column
	* @return shortest path found
	*/
	public static int explorePath(char[][] grid, boolean[][] processed, int[][] pathLen, int r, int c) {
	Queue<int[]> ngbs = new LinkedList<int[]>();
	ngbs.add(new int[]{r, c});
	while(!ngbs.isEmpty()) {
	int[] ngb = ngbs.poll();
	int currentR = ngb[0];
	int currentC = ngb[1];
	int currLen = pathLen[currentR][currentC];
	if (grid[currentR][currentC] == '#') {
	return currLen;
	}
	int[] deltaR = {-1, 0, 1, 0};
	int[] deltaC = {0, 1, 0, -1};
	for(int i = 0; i <= 3; i++) {
	int neighborR = currentR + deltaR[i];
	int neighborC = currentC + deltaC[i];
	if (isPermitted(grid, neighborR, neighborC) && !processed[neighborR][neighborC]) {
	pathLen[neighborR][neighborC] = currLen + 1; // set length of neighbor
	ngbs.add(new int[]{neighborR, neighborC});
	processed[neighborR][neighborC] = true;
	}
	}
	}
	return -1;
	} // explorePath
	// ---------------------------------------------------------------------------------------------------
	/**
	* determine if a given location is permissible to move or not
	* @param grid input matrix
	* @param r given location's row
	* @param c given location's column
	* @return boolean whether the location is permitted or not
	*/
	public static boolean isPermitted(char[][] grid, int r, int c) {
	if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length) {
	return grid[r][c] != 'X';
	}
	return false;
	} // isPermitted
	// ---------------------------------------------------------------------------------------------------
	}

view raw MatrixShortestDistanceBFS.java hosted with ❤ by GitHub

---

---

---

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

	import java.util.Random;
	/**
	* This is a Shuffler class that can be used to shuffle given input array
	* uniformly
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class Shuffler {
	private Random random;
	/**
	* Constructor to Shuffler instance.
	* initializes the variable random
	*
	*/
	public Shuffler() {
	random = new Random();
	} // Shuffler
	//----------------------------------------------------------------------------
	/**
	* returns random number between two given range
	* @param lo lower limit of the range
	* @param hi upper limit of the range
	*/
	private int getRandom(int lo, int hi) {
	return random.nextInt(hi - lo + 1) + lo;
	} // getRandom
	//----------------------------------------------------------------------------
	/**
	* swaps two items in the given array
	* @param nums input array in which swapping will be done
	* @param i first index to swap
	* @param j second index to swap
	*/
	private void swap(int[] nums, int i, int j) {
	int temp = nums[i];
	nums[i] = nums[j];
	nums[j] = temp;
	} // swap
	//----------------------------------------------------------------------------
	/**
	* methods that shuffles the given array
	* @param nums array to shuffle
	*/
	public void shuffle(int[] nums) {
	for (int i = 0; i < nums.length - 1 ; i++ ) {
	int rand = getRandom(i, nums.length-1);
	swap(nums, i, rand);
	}
	} // shuffle
	//----------------------------------------------------------------------------
	/**
	* driver method
	*/
	public static void main(String[] args) {
	int[] nums = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	Shuffler shuffler = new Shuffler();
	shuffler.shuffle(nums);
	for (int item : nums) {
	System.out.print(item + " ");
	}
	} // main
	//----------------------------------------------------------------------------
	} // Shuffler

view raw Shuffler.java hosted with ❤ by GitHub

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.

	/* File: WordCounter.java
	* Created: 5/14/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart Inc.
	*/
	import java.util.ArrayList;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Set;
	/**
	* Utility Class to capture the words in the given input string delimited
	* by pre-defined delimiters
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class WordCounter {
	private static Set<Character> delimiters = new HashSet<>();
	static {
	delimiters.add(' ');
	delimiters.add('\'');
	delimiters.add('!');
	delimiters.add('-');
	delimiters.add('(');
	delimiters.add(')');
	delimiters.add('{');
	delimiters.add('}');
	delimiters.add('[');
	delimiters.add(']');
	delimiters.add('?');
	delimiters.add('/');
	delimiters.add('\\');
	delimiters.add(',');
	}
	//---------------------------------------------------------------------------------------------
	/**
	* driver method
	* @param args
	*/
	public static void main(String[] args) {
	System.out.println(count("I am lord,voldemort")); // 4
	System.out.println(getWords("I am lord,voldemort")); // 4
	System.out.println(count("I am lord voldemort ")); // 4
	System.out.println(getWords("I am lord voldemort ")); // 4
	System.out.println(count(" I am lord voldemort")); // 4
	System.out.println(getWords(" I am lord voldemort")); // 4
	System.out.println(count(" I am lord voldemort ")); // 4
	System.out.println(getWords(" I am lord voldemort ")); // 4
	System.out.println(count(" Lord Voldemort! is my past, my present and my future!!!! ")); // 10
	System.out.println(getWords(" Lord Voldemort! is my past, my present and my future!!!! ")); // 4
	} // main
	//---------------------------------------------------------------------------------------------
	/**
	* Counts the number of words in the given input string
	* @param input input string
	* @return number of words in the input
	*/
	public static int count(String input) {
	boolean delimiter = true;
	int count = 0;
	for (int i = 0; i < input.length(); i++) {
	if (delimiters.contains(input.charAt(i))) { // delimiter encountered
	delimiter = true;
	} else {
	if (delimiter) { // first non delimiter encountered after sequence of delimiters, increase word count
	count++;
	}
	delimiter = false;
	}
	}
	return count;
	} // count
	//---------------------------------------------------------------------------------------------
	/**
	* Gets the list words in the input string
	* @param input input string
	* @return List of words in the input
	*/
	public static List<String> getWords(String input) {
	List<String> result = new ArrayList<>();
	boolean delimiter = true;
	//int count = 0;
	int wordStart = 0;
	for (int i = 0; i < input.length(); i++) {
	if (delimiters.contains(input.charAt(i))) { // delimiter encountered
	if (!delimiter) { // first delimiter after sequence of non delimiters, capture word
	result.add(input.substring(wordStart, i));
	}
	delimiter = true;
	} else {
	if (delimiter) {
	wordStart = i;
	//count++;
	}
	delimiter = false;
	}
	}
	if (!delimiter) {
	result.add(input.substring(wordStart));
	}
	return result;
	} // getWords
	//---------------------------------------------------------------------------------------------
	} // WordCounter

view raw WordCounter.java hosted with ❤ by GitHub

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

	//-----------------------------------------------------------------------------------
	/**
	* Detects a loop in a given LinkedList
	* Based upon keeping track of already visited Nodes
	* @param head head of the LinkedList
	* @return start of loop if it exists, otherwise null
	*/
	public Node detectLoop(Node head) {
	Set<Node> visitedNodes = new HashSet<Node>();
	Node node = head;
	while (node != null) {
	if (visitedNodes.contains(node)) { // loop detected. node is the start of the loop
	return node;
	} else {
	visitedNodes.add(node);
	node = node.next;
	}
	}
	return null; // no loop
	} // detectLoop
	//------------------------------------------------------------------------------------

view raw DetectLoopInLinkedList.java hosted with ❤ by GitHub

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

	Node faster = head;
	Node slower = head;
	// detect loop
	while (faster != null && faster.next != null) {
	faster = faster.next.next;
	slower = slower.next;
	if (faster == slower) { // loop detected
	break;
	}
	}
	if (faster != slower) return null; // loop not detected

view raw DetectLoopInLinkedList.java hosted with ❤ by GitHub

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.

	// detect start of loop
	faster = head;
	while (faster != slower) {
	faster = faster.next;
	slower = slower.next;
	}
	return faster;

view raw DetectLoopInLinkedList.java hosted with ❤ by GitHub

Complete Implementation

	/* File: DetectLoopInLinkedList.java
	* Created: 2018-05-09
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwart
	*/
	import java.util.HashSet;
	import java.util.Set;
	/**
	* Detect Loop in a Linked List
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class DetectLoopInLinkedList {
	public static void main(String[] args) {
	DetectLoopInLinkedList detectLoopInLinkedList = new DetectLoopInLinkedList();
	int i = 1;
	Node head = detectLoopInLinkedList.new Node(i++);
	Node tail = head;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++); // 11
	tail = tail.next;
	Node loopBegin = tail;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	tail = tail.next;
	tail.next = detectLoopInLinkedList.new Node(i++);
	// No Loop
	Node loopStart1 = detectLoopInLinkedList.detectLoop(head);
	Node loopStart2 = detectLoopInLinkedList.detectLoopFloydMethod(head);
	System.out.println(loopStart1 == null && loopStart2 == null ? "SUCCESS: Loop Not Found" : "Failure");
	// Crate Loop at 11
	tail = tail.next;
	tail.next = loopBegin;
	loopStart1 = detectLoopInLinkedList.detectLoop(head);
	loopStart2 = detectLoopInLinkedList.detectLoopFloydMethod(head);
	System.out.println(loopStart1 == loopStart2 ? "SUCCESS: Loop Start Found: " + loopStart1.value : "Failure");
	} // main
	//-----------------------------------------------------------------------------------
	/**
	* Detects a loop in a given LinkedList
	* Based upon keeping track of already visited Nodes
	* @param head head of the LinkedList
	* @return start of loop if it exists, otherwise null
	*/
	public Node detectLoop(Node head) {
	Set<Node> visitedNodes = new HashSet<Node>();
	Node node = head;
	while (node != null) {
	if (visitedNodes.contains(node)) { // loop detected. node is the start of the loop
	return node;
	} else {
	visitedNodes.add(node);
	node = node.next;
	}
	}
	return null; // no loop
	} // detectLoop
	//------------------------------------------------------------------------------------
	/**
	* Detect Loop in a LinkedList using Floyd's Method
	* @param head Head of the LinkedList
	* @return start of loop if it exists, otherwise null
	*/
	public Node detectLoopFloydMethod(Node head) {
	Node faster = head;
	Node slower = head;
	// detect loop
	while (faster != null && faster.next != null) {
	faster = faster.next.next;
	slower = slower.next;
	if (faster == slower) { // loop detected
	break;
	}
	}
	if (faster != slower) return null; // loop not detected
	// detect start of loop
	faster = head;
	while (faster != slower) {
	faster = faster.next;
	slower = slower.next;
	}
	return faster;
	} // detectLoopFloydMethod
	//------------------------------------------------------------------------------------
	/**
	* Class to represent Linked List Node
	*/
	public class Node {
	Node next;
	int value;
	public Node(int value) {
	this.value = value;
	} // Node
	} // Node
	} // DetectLoopInLinkedList

view raw DetectLoopInLinkedList.java hosted with ❤ by GitHub

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.

	/* File: StaticMethodsTest.java
	* Created: 2018-05-03
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 Hogwarts.
	*/
	package com.worldlingo;
	import junit.framework.Assert;
	import org.junit.Test;
	import org.junit.runner.RunWith;
	import org.mockito.Mockito;
	import org.powermock.api.mockito.PowerMockito;
	import org.powermock.core.classloader.annotations.PrepareForTest;
	import org.powermock.modules.junit4.PowerMockRunner;
	/**
	* JUnit test cases using PowerMockito for the Static Methods in a Class
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	@RunWith(PowerMockRunner.class)
	@PrepareForTest({TestClass.class})
	public class StaticMethodsTest {
	/**
	* PowerMockito.mockStatic(); mocks all the static methods in a class
	* So even you explicitly define mocked return for the static method,
	* execution of the method in the test will still be mocked and won't execute
	* its actual code. Instead it will return null (or appropriate value) if it
	* has return value.
	*
	* @throws Exception
	*/
	@Test
	public void test() throws Exception {
	PowerMockito.mockStatic(TestClass.class);
	PowerMockito.doReturn("TOM").when(TestClass.class, "toUpperCase", Mockito.anyString());
	String result1 = TestClass.toUpperCase("I am the king");
	String result2 = TestClass.toLowerCase("I am the king");
	String result3 = TestClass.alterWords("I am the king");
	Assert.assertEquals("TOM", result1);
	Assert.assertNull(result2);
	Assert.assertNull(result3);
	} // test
	//-----------------------------------------------------------------------------------------------
	/**
	* Similar to first test method
	* All static methods will be mocked
	* Here return value for each static methods are defined, and results are as expected
	*
	* @throws Exception
	*/
	@Test
	public void test2() throws Exception {
	PowerMockito.mockStatic(TestClass.class);
	PowerMockito.doReturn("TOM").when(TestClass.class, "toUpperCase", Mockito.anyString());
	PowerMockito.doReturn("marvolo").when(TestClass.class, "toLowerCase", Mockito.anyString());
	PowerMockito.doReturn("VoLdEmOrT").when(TestClass.class, "alterWords", Mockito.anyString());
	String result1 = TestClass.toUpperCase("I am the king");
	String result2 = TestClass.toLowerCase("I am the king");
	String result3 = TestClass.alterWords("I am the king");
	Assert.assertEquals("TOM", result1);
	Assert.assertEquals("marvolo", result2);
	Assert.assertEquals("VoLdEmOrT", result3);
	} // test2
	//------------------------------------------------------------------------------------------------
	/**
	* Mock individual Static method
	* Here TestClass.toUpperCase() and TestClass.toLowerCase() are mocked
	* but TestClass.alterWords() is not
	* So TestClass.alterWords() will actually execute the original code which
	* in turn invokes the methods toUpperCase() and toLowerCase(). Since these
	* are mocked, mocked results will be returned.
	*
	* @throws Exception
	*/
	@Test
	public void test3() throws Exception {
	PowerMockito.spy(TestClass.class);
	PowerMockito.doReturn("TOM").when(TestClass.class, "toUpperCase", Mockito.anyString());
	PowerMockito.doReturn("marvolo").when(TestClass.class, "toLowerCase", Mockito.anyString());
	String result1 = TestClass.toUpperCase("I am the king");
	String result2 = TestClass.toLowerCase("I am the king");
	String result3 = TestClass.alterWords("I am the king");
	Assert.assertEquals("TOM", result1);
	Assert.assertEquals("marvolo", result2);
	Assert.assertEquals("TOM marvolo TOM marvolo ", result3);
	} // test3
	} // StaticMethodsTest
	//-----------------------------------------------------------------------------------------
	/**
	* Test class with Static Methods
	*/
	class TestClass {
	public static String toUpperCase(String input) {
	return input.toUpperCase();
	} // toUpperCase
	//---------------------------------------------------------------------------------------
	public static String toLowerCase(String input) {
	return input.toLowerCase();
	} // toLowerCase
	//---------------------------------------------------------------------------------------
	public static String alterWords(String input) {
	String[] comps = input.split(" ");
	StringBuilder sb = new StringBuilder();
	boolean alt = true;
	for (String comp : comps) {
	if (alt) {
	sb.append(toUpperCase(comp)).append(" ");
	} else {
	sb.append(toLowerCase(comp)).append(" ");
	}
	alt = !alt;
	}
	return sb.toString();
	} // alterWords
	//----------------------------------------------------------------------------------------
	} // TestClass

view raw StaticMethodsTest.java hosted with ❤ by GitHub

---

---

---