Coin change problem-I (Number of ways to make a change) in Java.

This is another interesting problem that can be solved using dynamic programming. In this problem we have coins of different denominations {C1, C2, C3, C4.……Cn} and an amount S, then in how many ways we can make change for S amount using n coins. For example if we have coins of denominations 1, 2, 5 then for making change for amount 6 various ways are {1,1,1,1,1,1}, {1,1,1,1,2}, {2,2,2}, {1,1,2,2}, {1,5}. So there are 4 ways to make change for amount 6 using {1,2,5} coins.

Lets say that W(i, s) be total number of ways to make change for s amount using i coins. Then W(i, s) can be expressed as:
W(i, s) = W(i-1, s) + W(i, s-c[i])

W(i-1, s) --> total number of ways to make change for s amount without using ith coin.
W(i, s-c[i]) --> all ways that include atleast one ith coin

So total number of ways is sum of 2 different sub problems thus it has optimal substructure property.

There are few boundary conditions for above function:
1. W(i, s) = 1, if i >=0 and s = 0.
if we have no amount to make change but we have coins then there is only one way which is using no coins at all.
2. W(i, s) = 0, if i = 0 and s > 0
i.e. there is an amount for making change but we have no coins to make change then there is 0 way to make change.
3. W(i, s) = W(i-1, s), if s < c[i]
 if amount s is less than value of coin than number of ways is equal to ways in which ith coin is not included.
4. W(i, s) = W(i-1, s) + W(i, s-c[i]), if i>=1 and s>=c[i]
if number of coins greater than equal to 1 and amount s greater than equal to value of coins then number of ways is sum of ways without ith coin and ways that include atleast one occurence of ith coin.

To solve this problem we can call above function recursively taking care of base cases discuss above. But in that case there are lot of repetitive recursive calls. So this problem also has overlapping sub-problems property.
Below is recursive approach without using dynamic programming.

public class CoinChange {      static int numOfWaysRecursive(int [] coins, int i, int amount){     if(amount==0){       return 1;     }     if(i < 0){       return 0;     }     if(amount < coins[i]){       return numOfWaysRecursive(coins, i-1, amount);     }else{       return numOfWaysRecursive(coins, i-1, amount) + numOfWaysRecursive(coins, i, amount-coins[i]);     }   }      public static void main(String[] args) {     System.out.println("Number of ways:"+numOfWaysRecursive(new int[]{1,5,10},2,5371));   } }

Java2html

Number of ways:289444

We can improve performance by using bottom up dynamic programming using tabulation instead of using recursion. Below is bottom up dynamic programming solution to problem.

public class CoinChange {   static int numOfWays(int [] coins, int amount){     int [][] ways = new int[coins.length][amount+1];     for (int i = 0; i < coins.length; i++) {       ways[i][0] = 1;     }     for (int i = 1; i <= amount; i++) {       ways[0][i] = 0;     }     int j = 0;     for (int i = 1; i < coins.length; i++) {       for (j = 1; j < coins[i]; j++) {         ways[i][j] = ways[i-1][j];       }       for (; j <= amount; j++) {         ways[i][j] = ways[i-1][j] + ways[i][j - coins[i]];       }     }     return ways[coins.length-1][amount];   }      public static void main(String[] args) {     System.out.println("Number of ways:"+numOfWays(new int[]{0,1,5,10},5371));   } }

Java2html

Number of ways:289444

In above solution we are storing number of ways for each coin in 2-D array. We can optimize to use only 1-D array since every time loop runs 1-D array contain number of ways till previous coin.Memory optimize version of above solutions is:

static int numOfWays1(int [] coins, int amount){   int [] ways = new int[amount+1];   ways[0] = 1;   for (int i = 0; i < coins.length; i++) {     for (int j = coins[i]; j <= amount; j++) {       ways[j]+=ways[j-coins[i]];     }   }   return ways[amount]; }

Java2html

Counting number of set bits in an integer.

In binary representation of an integer bit 1 is called set bit. Calculating number of set bits in an integer is an interesting question that is asked sometimes in programming interview. There is a method in JDK using which we can calculate number of set bits in an integer which is Integer.bitCount(). Its implementation is little bit complex and different from below discussed 2 methods.  
Integer.bitCount() implementation from JDK 6.

public static int bitCount(int i) {         // HD, Figure 5-2         i = i - ((i >>> 1) & 0x55555555);         i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);         i = (i + (i >>> 4)) & 0x0f0f0f0f;         i = i + (i >>> 8);         i = i + (i >>> 16);         return i & 0x3f;     }

Java2html

In this post we will see how number of set bits can be calculated without using Java api Integer.bitCount() method.
In first method we use & (bitwise AND operation) and >>> operator (logical right shift operator) to calculate number of set bits.

import java.util.Scanner; /*Program to calculate number   * of set bits in an integer using   * bit shifting and masking.  * @author Anuj  *   * */ public class NumberOfBits {          static int calculateSetBits(int n){         int count = 0;         while(n!=0){             if((n & 1)==1){                 count++;             }             n>>>=1;         }         return count;     }     public static void main(String[] args) {         System.out.print("Enter number:");         Scanner sc = new Scanner(System.in);         int num = sc.nextInt();         System.out.println("Number of set bits in "+num+" are:"+calculateSetBits(num));     } }

Java2html

Output for input value of 127 and -1.

Enter number:127
Number of set bits in 127 are:7

Enter number:-1
Number of set bits in -1 are:32

Explanation:
In while loop number is applied & operator (bitwise AND) with 1 to check if least significant bit is one, if it is one than count is increased by one.  And after that bits in number is shifted one place right by using >>> (logical right shift operator). Loops keep on running until number becomes 0 due to right shift of bits.
In above program while loop runs for each bits in an integer i.e. 32 times.

There is another way to calculate number of set bits in an integer more efficiently by using Brian Kernighan’s algorithm. In this algorithm while loop runs only as many times as number of set bits in an integer. For example, 128 has only one set bit and if we calculate using above method of masking and bit shifting while loop will run 32 times but by using Brian Kernighan’s method it will run only one time.

Brian Kernighan algorithm implementation.

static int brianKernighanMethod(int num){         int count = 0;         while (num!=0) {             num = num & (num-1);             count++;         }         return count;     }

Java2html

Explanation:
Least significant it of an integer can be either 0 or 1. If-
1. Least significant bit of integer n is 1 then n-1 has 0 in LSB position and if we do bitwise AND between n and n-1 the resulting number has 0 in LSB position.
2. If LSB is 0 then all bits starting from LSB till first occuring 1 bit is toggled. For example if binary representation of n is 10100 then n-1 is 10011. In this case also the first place where 1 bit occurs starting from LSB becomes 0 in original number after bitwise AND with n-1.

The point to not that in Brian Kernighan’s method of finding number of set bits the number of times loop run is equal to number of set bits. So if number is 128 whose binary representation is 10000000 having only one set bit, then using Brian Kernighan’s method loop will run only one time.

Longest Common Subsequence using dynamic programming in Java.

A subsequence is a sequence that is derived from a sequence such that all characters in subsequence are in same order as original sequence but may not be contiguous. For example, if we have a sequence ABDGTPWYZ, then BDTY is its subsequence, BDGT, ADTWZ are also its subsequences. So in longest common subsequence (LCS) there are 2 sequences given and we have to find length of longest subsequence that is present in both. For example, if we have 2 subsequences ABHKLMNYZ and XBMKLTNWZ then subsequence BKLNZ is longest subsequence that is common in both  and its length is 5.

If 2 sequences are  X_{i and} Y_{j, where i and j are their length repectively and LCS( Xi,Yj)} is length of longest common subsequence, then below is recursive defination of LCS.

_{Explanation of above recursive function}

_{1. If ith position character in seqeunce X is equal to character at jth position of sequence Y then length of subsequence increases by 1 and is equal to 1 + LCS of remaining i-1 characters of X and j-1 characters of Y.} 

_{2. If ith position character in X is not equal to jth position character in Y then answer is maximum of LCS of i characters of X and j-1 characters of Y or LCS of i-1 charcters of X and j charcters of Y.}

<sub>3. If length of either sequence becomes 0 comparaing then value of 0 is returned.

Java Code for bottoms up dynamic programming using tabulation is-</sub>

package com.anuj.dp; import java.util.Scanner; /*  * Calculation of length of longest common   * subsequence of given two sequences using   * bottom up dynamic programming and tabulation.  * @author Anuj  * */ public class LCS {          private static int findlcs(String seq1, String seq2){         int x = seq1.length();         int y = seq2.length();         int [][] lcs = new int[x+1][y+1];                  for (int i = 0; i <= x; i++) {             for (int j = 0; j <= y; j++) {                 if(i ==0 || j == 0){                     lcs[i][j] = 0;                 }else if(seq1.charAt(i-1)==seq2.charAt(j-1)){                     lcs[i][j] = 1 + lcs[i-1][j-1];                 }else if(seq1.charAt(i-1)!=seq2.charAt(j-1)){                     lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);                 }             }         }         return lcs[x][y];     }          private static int max(int a, int b){         return (a > b)? a : b;     }          public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         String seq1 = sc.next();         String seq2 = sc.next();         System.out.println("sequence1="+seq1+" sequence2="+seq2);         System.out.println("Length of longest common subsequence is:"+findlcs(seq1, seq2));     } }

Java2html

_Input:

ASDGHJPL
WSFDHPLJ

Output:

sequence1=ASDGHJPL sequence2=WSFDHPLJ
Length of longest common subsequence is:5

Explanation: In above solution we starts comparing characters in sequences from beginning and apply above function rules for lcs at each comparison. The table that is constructed when program finish is:

If characters at i and j are equal then we add 1 to value present in i-1 and j-1 cell. If character at i and j position are not equal then we pick maximum of value at i-1, j or i, j-1. After table is filled completely we check last value in table for length of LCS.

We can also find longest common subsequence value using below code:

int a = 1, b = 1;         System.out.print("Longest common sequence is:");         while (a <= x && b <= y) {             if(seq1.charAt(a-1)==seq2.charAt(b-1)){                 System.out.print(seq1.charAt(a-1));                 a++;                 b++;             }else if(lcs[a+1][b] > lcs[a][b+1]){                 a++;             }else{                 b++;             }         }

Java2html

Add this code in findlcs() method before return statement. In this method we start from begining of sequences and check if character at that index is equal than it is part of LCS and print it and increment both sequences index by 1 and if character are not equal then value at one cell below is compared with one cell to right i.e. value at a+1, b is compared with a, b+1 and we go to right if right cell has greater value or cell below if below cell has greater value and then again characters of sequences are compared at new position and if characters at that position are equal it is printed and after loop finished we have value LCS printed on console.

Warshall algorithm in Graph in Java.

In directed graph if we starts from a vertex we may not be able to reach some vertices. For example consider below graph, if we start from vertex D we can only reach C other vertices are unreachable from D. In some graph applications we need to know which vertices we can reach if we starts from a particular vertex.

Fig 1

Using Warshall algorithm we can modify adjacency matrix of graph to generate transistive closure of graph using which we can know what all vertices are reachable from a particular vertex. For finding transistive closure using warshall algorithm we modify adjacency matrix whenever we find transitive property between vertices for connections. For example in above graph there is an edge from A to D and another edge from D to C, so there is path from A to C and we modify entry for row A and column C in adjacency matrix to indicate connection.

Consider below directed graph. Using below java code for warshall algorithm we will find transistve closure for below graph.

Fig 2

Java code:

001 /*Warshall Algorithm to find Transistive Closure  002  * of a Directed Graph. 003  * @author Anuj 004  * */ 005 public class Warshall { 006         private Graph graph; 007          008         /* 009          * Adding vertices and Edges to  010          * graph. 011          * */ 012         private void setGraph(){ 013                 graph = new Graph(5); 014                 graph.addVertex('A'); 015                 graph.addVertex('B'); 016                 graph.addVertex('C'); 017                 graph.addVertex('D'); 018                 graph.addVertex('E'); 019                  020                 graph.addEdge(0, 1); 021                 graph.addEdge(1, 2); 022                 graph.addEdge(2, 4); 023                 graph.addEdge(3, 1); 024                 graph.addEdge(3, 4); 025         } 026          027         /* 028          * In this method warshall algorithm runs. 029          *Adjacency Matrix of a directed graph is modified to  030          *generate transistive closure of graph.  031          * */ 032         private void warshallAlgo(){ 033                 int numVerts = graph.numVerts; 034                  035                 for (int k = 0; k < numVerts; k++) { 036                         for (int i = 0; i < numVerts; i++) { 037                                 if(graph.adjMatrix[i][k]==0){ 038                                         continue; 039                                 } 040                                 for (int j = 0; j < numVerts; j++) { 041                                         if(graph.adjMatrix[k][j]==1){ 042                                                 graph.adjMatrix[i][j] = 1; 043                                         } 044                                 } 045                         } 046                 } 047         } 048  049         public static void main(String[] args) { 050                 Warshall warshall = new Warshall(); 051                 warshall.setGraph(); 052                 System.out.println("Adjacency matrix of Graph is:"); 053                 warshall.graph.displayMatrx(warshall.graph.adjMatrix); 054                 System.out.println(); 055                 warshall.warshallAlgo(); 056                 //Adjacency matrix is modified to generate transistive closure  057                 //in method warshallAlgo(). 058                 System.out.println("Transistive Closure of Graph is:"); 059                 warshall.graph.displayMatrx(warshall.graph.adjMatrix); 060         } 061 } 062  063  064 class Graph{ 065      int maxVertsNum; 066          int numVerts; 067          Vertex [] vertexList; 068          int [][] adjMatrix; 069          070         public Graph(int maxVerts){ 071                 maxVertsNum = maxVerts; 072                 numVerts = 0; 073                 vertexList = new Vertex[maxVertsNum]; 074                 adjMatrix = new int[maxVertsNum][maxVertsNum]; 075                 //Initializing all entries to zero. 076                 for (int i = 0; i < maxVertsNum; i++) { 077                         for (int j = 0; j < maxVertsNum; j++) { 078                                 adjMatrix[i][j] = 0; 079                         } 080                 } 081         } 082          083         public void addVertex(char label){ 084                 if(numVerts < maxVertsNum){ 085                         vertexList[numVerts++] = new Vertex(label); 086                 } 087         } 088          089         /* 090          * Adding an edge to a directed graph. 091          * */ 092         public void addEdge(int start, int end){ 093                 if(start < numVerts && end < numVerts){ 094                         adjMatrix[start][end] = 1; 095                 } 096         } 097          098         public void display(int idx){ 099                 System.out.print(vertexList[idx].label); 100         } 101          102         /* 103          * Method to display 2-D array in row  104          * and column form with labels of vertices in  105          * row and column. 106          * */ 107         public void displayMatrx(int [][] array){ 108                 System.out.print("  "); 109                 for (int i = 0; i < numVerts; i++) { 110                         System.out.print(vertexList[i].label+" "); 111                 } 112                 System.out.println(); 113                 for (int i = 0; i < numVerts; i++) { 114                         System.out.print(vertexList[i].label+" "); 115                         for (int j = 0; j < numVerts; j++) { 116                                 System.out.print(array[i][j]+" "); 117                         } 118                         System.out.println(); 119                 } 120         } 121 } 122  123 class Vertex{ 124         char label; 125          126         public Vertex(char label){ 127                 this.label = label; 128         } 129 }

Java2html

Output: 

Adjacency matrix of Graph is:
  A B C D E 
A 0 1 0 0 0 
B 0 0 1 0 0 
C 0 0 0 0 1 
D 0 1 0 0 1 
E 0 0 0 0 0 

Transistive Closure of Graph is:
  A B C D E 
A 0 1 1 0 1 
B 0 0 1 0 1 
C 0 0 0 0 1 
D 0 1 1 0 1 
E 0 0 0 0 0 

Explanation:
In warshall algorithm for finding transitive closure of graph we modify adjacency matrix of graph. For example in Fig 2 graph if there is an edge from A to B and another edge from B to C then A and C are connected and we modify entry in adjacency matrix to enter 1 for row A and column C. In above code method warshallAlgo contains logic for warshall algorithm. There are 3 for loops used in warshall algorithm. Vertex represented by outermost for loop using int variable k acts as intermediate vertex like B in example I just mentioned above that is connected with 2 different vertex. In 1st inner for loop with i as loop variable we check for all vertices if there is an edge to vertices represented by outermost loop i.e. an edge from i to k, if there is no edge we do not go to 2nd inner for loop and continue with next iteration of 1st inner for loop. 2nd inner loop having j as loop variable is entered only when there is an edge from i to k. In 2nd for loop we check if there is an edge from vertices of outermost for loop to in the direction of vertices of 2nd inner for loop i.e. an edge from k to j. If there an edge from k to j thats mean i to j is a connected path and we modify adjacency matrix entry for row i and column j.
Warshall algorithm has time complexity of O(N^3). But after transistive closure has been generated it will take only O(1) time to find if a vertex is reachable from a particular vertex.