Maximize trailing zeros in product from top left to bottom right of given Matrix | Java program for the above approach ; Create a class pair to store count of 2 ' s ▁ and ▁ 5' s ; Parameterized Constructor ; Function to covert into Strings ; Function to get maximum no of zeros in product of path from topleft to bottom right ; Base Case ; Store the maximum count of zeros till ith and jth index ; Initialize the ( 0 , 0 ) ; Initialize the first row and column explicitly ; Iterate through all the cells ; Get the pair from the top and from left ; If there are more number of 0 s from top or left ; Print the no of zeros min ( no of 2 ' s , ▁ no ▁ of ▁ 5' s ) ; Function to calculate no of zeros ; Function to calculate no of 2 's ; Return the final count ; Function to calculate no of 5 's ; Return the final count ; Function to add pairs ; Return the resultant pair ; Driver Code ; Given N & M ; Given matrix ; Function Call
import java . io . * ; import java . util . * ; class pair { int x , y ; pair ( int x , int y ) { this . x = x ; this . y = y ; } public String toString ( ) { return " ( " + this . x + " , ▁ " + this . y + " ) " ; } } class GFG { public static void maxZeros ( int [ ] [ ] mat , int n , int m ) { if ( n == 0 m == 0 ) return ; pair dp [ ] [ ] = new pair [ n + 1 ] [ m + 1 ] ; dp [ 0 ] [ 0 ] = new pair ( countTwos ( mat [ 0 ] [ 0 ] ) , countFives ( mat [ 0 ] [ 0 ] ) ) ; for ( int i = 1 ; i < n ; i ++ ) dp [ i ] [ 0 ] = add ( dp [ i - 1 ] [ 0 ] , new pair ( countTwos ( mat [ i ] [ 0 ] ) , countFives ( mat [ i ] [ 0 ] ) ) ) ; for ( int i = 1 ; i < m ; i ++ ) dp [ 0 ] [ i ] = add ( dp [ 0 ] [ i - 1 ] , new pair ( countTwos ( mat [ 0 ] [ i ] ) , countFives ( mat [ 0 ] [ i ] ) ) ) ; for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 1 ; j < m ; j ++ ) { pair top = dp [ i - 1 ] [ j ] ; pair left = dp [ i ] [ j - 1 ] ; pair curr = new pair ( countTwos ( mat [ i ] [ j ] ) , countFives ( mat [ i ] [ j ] ) ) ; top = add ( top , curr ) ; left = add ( left , curr ) ; if ( check ( top , left ) ) dp [ i ] [ j ] = top ; else dp [ i ] [ j ] = left ; } } System . out . println ( Math . min ( dp [ n - 1 ] [ m - 1 ] . x , dp [ n - 1 ] [ m - 1 ] . y ) ) ; } public static boolean check ( pair one , pair two ) { int top = Math . min ( one . x , one . y ) ; int left = Math . min ( two . x , two . y ) ; if ( top > left ) return true ; else return false ; } public static int countTwos ( int num ) { int count = 0 ; while ( num != 0 && num % 2 == 0 ) { num /= 2 ; count ++ ; } return count ; } public static int countFives ( int num ) { int count = 0 ; while ( num != 0 && num % 5 == 0 ) { num /= 5 ; count ++ ; } return count ; } public static pair add ( pair one , pair two ) { pair np = new pair ( one . x + two . x , one . y + two . y ) ; return np ; } public static void main ( String [ ] args ) { int N = 3 , M = 4 ; int mat [ ] [ ] = { { 6 , 25 , 4 , 10 } , { 12 , 25 , 1 , 15 } , { 7 , 15 , 15 , 5 } } ; maxZeros ( mat , N , M ) ; } }