Given a matrix mat[][] of dimensions N * M,
the task is to print the maximum number of trailing zeros that can be obtained in the product of matrix elements in the path from the top-left cell (0, 0) to the bottom-right cell (N – 1, M – 1) of the given matrix. Only possible moves from any cell (i, j) is (i + 1, j) or (i, j + 1).
Examples:
Input: N = 3, M = 4, mat[][] = {{6, 25, 4, 10}, {12, 25, 1, 15}, {7, 15, 15, 5}}
Output: 4
Explanation: Among all possible paths from top left to bottom right, the path (6, 25, 4, 10, 15, 5} has product (= 450000) with maximum number of trailing 0s. Therefore, the count of zeros is 4.Input: N = 3, M = 3, mat[][] = {{2, 5, 2}, {10, 2, 40}, {5, 4, 8}}
Output: 2
Naive Approach: The idea is to generate all possible paths from the top-left cell (0, 0) to the bottom-right cell (N – 1, M – 1) of the given matrix recursively and calculate the product of elements in each path. Print the maximum no of trailing zeros among the products. Follow the steps below to solve the problem:
- Initialize a variable, say product to store the product of all possible elements on the path from the top-left cell (0, 0) to bottom-right cell (N – 1, M – 1).
- Below recurrence relation calculates the maxZeros value of all possible paths from the top-left cell (0, 0) to the bottom-right cell (N – 1, M – 1).
maxZeros(i, j, productValue) = max(maxZeros(i – 1, j, product*mat[i][j]), maxZeros(i, j – 1, product*mat[i][j]))
where,
maxZeros() is the function that returns the maximum number of trailing zeros.
- From the above recurrence relation generate all possible path recursively and when any path reaches the cell (N – 1, M – 1) then find the count of trailing zeros of the product till that path.
- When every recursive call ends, maximize the count of zeros returns by that recursive calls.
- Print the maximum number of trailing zeros after the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define N 3#define M 4// Stores the maximum count of zerosint zeros = 0;// Function that counts the trailing// zeros in the given number numint countZeros(int num){ // Stores the count of zeros int count = 0; // Iterate digits of num while (num > 0 && num % 10 == 0) { num /= 10; count++; } // Return the count return count;}// Function to count maximum trailing// zeros in product of elements in a// path from top-left to bottom-rightvoid maxZeros(int mat[][M], int i, int j, int product){ // If reached end of matrix if (i == N - 1 && j == M - 1) { // Count the no of zeros product product *= mat[i][j]; zeros = max(zeros, countZeros(product)); return; } // If out of bounds, return if (i >= N) return; if (j >= M) return; // Recurse with move (i+1, j) maxZeros(mat, i + 1, j, product * mat[i][j]); // Recurse with move(i, j+1) maxZeros(mat, i, j + 1, product * mat[i][j]);}// Function to print the maximum// count of trailing zeros obtainedvoid maxZerosUtil(int mat[][M], int i, int j, int product){ // Function Call maxZeros(mat, 0, 0, 1); // Print the maximum count cout << zeros << endl;}// Driver Codeint main(){ // Given matrix int mat[N][M] = { { 6, 25, 4, 10 }, { 12, 25, 1, 15 }, { 7, 15, 15, 5 } }; // Function Call maxZerosUtil(mat, 0, 0, 1);}// This code is contributed by bolliranadheer |
Java
// Java program for the above approachimport java.util.*;class GFG { // Stores the maximum count of zeros static int zeros = 0; // Function to count maximum trailing // zeros in product of elements in a // path from top-left to bottom-right public static void maxZeros(int[][] mat, int i, int j, int product) { // If reached end of matrix if (i == mat.length - 1 && j == mat[0].length - 1) { // Count the no of zeros product product *= mat[i][j]; zeros = Math.max(zeros, countZeros(product)); return; } // If out of bounds, return if (i >= mat.length) return; if (j >= mat[0].length) return; // Recurse with move (i+1, j) maxZeros(mat, i + 1, j, product * mat[i][j]); // Recurse with move(i, j+1) maxZeros(mat, i, j + 1, product * mat[i][j]); } // Function that counts the trailing // zeros in the given number num public static int countZeros(int num) { // Stores the count of zeros int count = 0; // Iterate digits of num while (num > 0 && num % 10 == 0) { num /= 10; count++; } // Return the count return count; } // Function to print the maximum // count of trailing zeros obtained public static void maxZerosUtil( int[][] mat, int i, int j, int product) { // Function Call maxZeros(mat, 0, 0, 1); // Print the maximum count System.out.println(zeros); } // Driver Code public static void main(String[] args) { // Given N & M int N = 3, M = 4; // Given matrix int mat[][] = { { 6, 25, 4, 10 }, { 12, 25, 1, 15 }, { 7, 15, 15, 5 } }; // Function Call maxZerosUtil(mat, 0, 0, 1); }} |
Python3
# Python3 program for the # above approachN = 3M = 4# Stores the maximum count # of zeroszeros = 0# Function that counts the # trailing zeros in the # given number numdef countZeros(num): # Stores the count of #zeros count = 0 # Iterate digits of # num while (num > 0 and num % 10 == 0): num //= 10 count += 1 # Return the count return count# Function to count maximum # trailing zeros in product # of elements in a path from # top-left to bottom-rightdef maxZeros(mat, i, j, product): global M global N # If reached end of # matrix if (i == N - 1 and j == M - 1): # Count the no of # zeros product product *= mat[i][j] global zeros zeros = max(zeros, countZeros(product)) return # If out of bounds, # return if (i >= N): return if (j >= M): return # Recurse with move # (i+1, j) maxZeros(mat, i + 1, j, product * mat[i][j]) # Recurse with move # (i, j+1) maxZeros(mat, i, j + 1, product * mat[i][j])# Function to print the # maximum count of trailing # zeros obtaineddef maxZerosUtil(mat, i, j, product): # Function Call maxZeros(mat, 0, 0, 1) # Print the maximum # count print(zeros)# Driver Codeif __name__ == "__main__": # Given matrix mat = [[6, 25, 4, 10], [12, 25, 1, 15], [7, 15, 15, 5]] # Function Call maxZerosUtil(mat, 0, 0, 1)# This code is contributed by Chitranayal |
C#
// C# program for the above approachusing System;class GFG{// Stores the maximum count of zerosstatic int zeros = 0;// Function to count maximum trailing// zeros in product of elements in a// path from top-left to bottom-rightpublic static void maxZeros(int[,] mat, int i, int j, int product, int N, int M){ // If reached end of matrix if (i == N - 1 && j == M - 1) { // Count the no of zeros product product *= mat[i, j]; zeros = Math.Max(zeros, countZeros(product)); return; } // If out of bounds, return if (i >= mat.GetLength(0)) return; if (j >= mat.GetLength(1)) return; // Recurse with move (i+1, j) maxZeros(mat, i + 1, j, product * mat[i, j], N, M); // Recurse with move(i, j+1) maxZeros(mat, i, j + 1, product * mat[i, j], N, M);}// Function that counts the trailing// zeros in the given number numpublic static int countZeros(int num){ // Stores the count of zeros int count = 0; // Iterate digits of num while (num > 0 && num % 10 == 0) { num /= 10; count++; } // Return the count return count;}// Function to print the maximum// count of trailing zeros obtainedpublic static void maxZerosUtil(int[,] mat, int i, int j, int product, int N, int M){ // Function Call maxZeros(mat, 0, 0, 1, N, M); // Print the maximum count Console.WriteLine(zeros);}// Driver Codepublic static void Main(String[] args){ // Given N & M int N = 3, M = 4; // Given matrix int [,]mat = { { 6, 25, 4, 10 }, { 12, 25, 1, 15 }, { 7, 15, 15, 5 } }; // Function Call maxZerosUtil(mat, 0, 0, 1, N, M);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program for the above approachvar N = 3var M = 4// Stores the maximum count of zerosvar zeros = 0;// Function that counts the trailing// zeros in the given number numfunction countZeros(num){ // Stores the count of zeros var count = 0; // Iterate digits of num while (num > 0 && num % 10 == 0) { num /= 10; count++; } // Return the count return count;}// Function to count maximum trailing// zeros in product of elements in a// path from top-left to bottom-rightfunction maxZeros(mat, i, j, product){ // If reached end of matrix if (i == N - 1 && j == M - 1) { // Count the no of zeros product product *= mat[i][j]; zeros = Math.max(zeros, countZeros(product)); return; } // If out of bounds, return if (i >= N) return; if (j >= M) return; // Recurse with move (i+1, j) maxZeros(mat, i + 1, j, product * mat[i][j]); // Recurse with move(i, j+1) maxZeros(mat, i, j + 1, product * mat[i][j]);}// Function to print the maximum// count of trailing zeros obtainedfunction maxZerosUtil(mat, i, j, product){ // Function Call maxZeros(mat, 0, 0, 1); // Print the maximum count document.write( zeros + "<br>");}// Driver Code// Given matrixvar mat = [ [ 6, 25, 4, 10 ], [ 12, 25, 1, 15 ], [ 7, 15, 15, 5 ]];// Function CallmaxZerosUtil(mat, 0, 0, 1);</script> |
Output
4
Time Complexity: O(2N*M)
Auxiliary Space: O(1)
Dynamic Programming using Bottom-Up Approach: The recursive calls in the above approach can be reduced using an auxiliary array dp[][] and calculate the value of each state in the bottom-up approach. Follow the steps below:
- Create an auxiliary array dp[][] of size N*M.
- dp[i][j] represents no of fives and twos till the ith row and jth column.
- Traverse the matrix and update each state of dp[][] array as:
dp[i][j] = max(dp[i – 1][j], dp[i][j – 1])
- Print the minimum of the respective count of (2s, 5s) after the above steps as the result.
Below is the implementation of the above approach:
Java
// Java program for the above approachimport java.io.*;import java.util.*;// Create a class pair to store// count of 2's and 5'sclass pair { int x, y; // Parameterized Constructor pair(int x, int y) { this.x = x; this.y = y; } // Function to convert into Strings public String toString() { return "(" + this.x + ", " + this.y + ")"; }}class GFG { // Function to get maximum no of // zeros in product of path from // topleft to bottom right public static void maxZeros( int[][] mat, int n, int m) { // Base Case if (n == 0 || m == 0) return; // Store the maximum count of // zeros till ith and jth index pair dp[][] = new pair[n + 1][m + 1]; // Initialize the (0, 0) dp[0][0] = new pair(countTwos(mat[0][0]), countFives(mat[0][0])); // Initialize the first row // and column explicitly 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]))); // Iterate through all the cells for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { // Get the pair from the // top and from left 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 there are more number // of 0s from top or left if (check(top, left)) dp[i][j] = top; else dp[i][j] = left; } } // Print the no of zeros // min(no of 2's, no of 5's) System.out.println( Math.min(dp[n - 1][m - 1].x, dp[n - 1][m - 1].y)); } // Function to calculate no of zeros 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; } // Function to calculate no of 2's public static int countTwos(int num) { int count = 0; while (num != 0 && num % 2 == 0) { num /= 2; count++; } // Return the final count return count; } // Function to calculate no of 5's public static int countFives(int num) { int count = 0; while (num != 0 && num % 5 == 0) { num /= 5; count++; } // Return the final count return count; } // Function to add pairs public static pair add(pair one, pair two) { pair np = new pair(one.x + two.x, one.y + two.y); // Return the resultant pair return np; } // Driver Code public static void main(String[] args) { // Given N & M int N = 3, M = 4; // Given matrix int mat[][] = { { 6, 25, 4, 10 }, { 12, 25, 1, 15 }, { 7, 15, 15, 5 } }; // Function Call maxZeros(mat, N, M); }} |
Python3
#Python code for the above approachimport math# Create a class pair to store# count of 2's and 5'sclass pair: def __init__(self, x, y): self.x = x self.y = y # Function to convert into Strings def __str__(self): return "(" + str(self.x) + ", " + str(self.y) + ")"# Function to get maximum no of# zeros in product of path from# topleft to bottom rightdef maxZeros(mat, n, m): # Base Case if n == 0 or m == 0: return # Store the maximum count of # zeros till ith and jth index dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)] # Initialize the (0, 0) dp[0][0] = pair(countTwos(mat[0][0]), countFives(mat[0][0])) # Initialize the first row and column explicitly for i in range(1, n): dp[i][0] = add(dp[i - 1][0], pair(countTwos(mat[i][0]), countFives(mat[i][0]))) for i in range(1, m): dp[0][i] = add(dp[0][i - 1], pair(countTwos(mat[0][i]), countFives(mat[0][i]))) # Iterate through all the cells for i in range(1, n): for j in range(1, m): # Get the pair from the top and from left top = dp[i - 1][j] left = dp[i][j - 1] curr = pair(countTwos(mat[i][j]), countFives(mat[i][j])) top = add(top, curr) left = add(left, curr) # If there are more number of 0s from top or left if check(top, left): dp[i][j] = top else: dp[i][j] = left # Print the no of zeros # min(no of 2's, no of 5's) print(min(dp[n - 1][m - 1].x, dp[n - 1][m - 1].y))# Function to calculate no of zerosdef check(one, two): top = min(one.x, one.y) left = min(two.x, two.y) if top > left: return True else: return False# Function to calculate no of 2'sdef countTwos(num): count = 0 while num != 0 and num % 2 == 0: num /= 2 count += 1 # Return the final count return count# Function to calculate no of 5'sdef countFives(num): count = 0 while num != 0 and num % 5 == 0: num /= 5 count += 1 return count# Function to add pairsdef add(one, two): np = pair(one.x + two.x, one.y + two.y) return np# test the code with a matrix # Given N & MN = 3;M = 4;#Given matrixmat = [[6, 25, 4, 10], [12, 25, 1, 15], [7, 15, 15, 5]];# Function CallmaxZeros(mat, N, M); |
C#
// C# program for the above approachusing System;// Create a class pair to store// count of 2's and 5'spublic class pair{ public int x, y; // Parameterized Constructor public pair(int x, int y) { this.x = x; this.y = y; } // Function to convert into Strings public String toString() { return "(" + this.x + ", " + this.y + ")"; }}class GFG{// Function to get maximum no of// zeros in product of path from// topleft to bottom rightpublic static void maxZeros(int[,] mat, int n, int m){ // Base Case if (n == 0 || m == 0) return; // Store the maximum count of // zeros till ith and jth index pair [,]dp = new pair[n + 1, m + 1]; // Initialize the (0, 0) dp[0, 0] = new pair(countTwos(mat[0, 0]), countFives(mat[0, 0])); // Initialize the first row // and column explicitly 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]))); // Iterate through all the cells for(int i = 1; i < n; i++) { for(int j = 1; j < m; j++) { // Get the pair from the // top and from left 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 there are more number // of 0s from top or left if (check(top, left)) dp[i, j] = top; else dp[i, j] = left; } } // Print the no of zeros // min(no of 2's, no of 5's) Console.WriteLine( Math.Min(dp[n - 1, m - 1].x, dp[n - 1, m - 1].y));}// Function to calculate no of zerospublic static bool 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;}// Function to calculate no of 2'spublic static int countTwos(int num){ int count = 0; while (num != 0 && num % 2 == 0) { num /= 2; count++; } // Return the readonly count return count;}// Function to calculate no of 5'spublic static int countFives(int num){ int count = 0; while (num != 0 && num % 5 == 0) { num /= 5; count++; } // Return the readonly count return count;}// Function to add pairspublic static pair add(pair one, pair two){ pair np = new pair(one.x + two.x, one.y + two.y); // Return the resultant pair return np;}// Driver Codepublic static void Main(String[] args){ // Given N & M int N = 3, M = 4; // Given matrix int [,]mat = { { 6, 25, 4, 10 }, { 12, 25, 1, 15 }, { 7, 15, 15, 5 } }; // Function Call maxZeros(mat, N, M);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Create a class pair to store// count of 2's and 5'sclass pair{ x = 0; y = 0; // Parameterized Constructor constructor(x, y) { this.x = x; this.y = y; } // Function to convert into Strings toString() { return "(" + this.x + ", " + this.y + ")"; }}class GFG{ // Function to get maximum no of // zeros in product of path from // topleft to bottom right static maxZeros(mat, n, m) { // Base Case if (n == 0 || m == 0) { return; } // Store the maximum count of // zeros till ith and jth index var dp = Array(n + 1).fill(null).map(()=>new Array(m + 1).fill(null)); // Initialize the (0, 0) dp[0][0] = new pair(GFG.countTwos(mat[0][0]), GFG.countFives(mat[0][0])); // Initialize the first row // and column explicitly for (let i=1; i < n; i++) { dp[i][0] = GFG.add(dp[i - 1][0], new pair(GFG.countTwos(mat[i][0]), GFG.countFives(mat[i][0]))); } for (let i=1; i < m; i++) { dp[0][i] = GFG.add(dp[0][i - 1], new pair(GFG.countTwos(mat[0][i]), GFG.countFives(mat[0][i]))); } // Iterate through all the cells for (let i=1; i < n; i++) { for (let j=1; j < m; j++) { // Get the pair from the // top and from left var top = dp[i - 1][j]; var left = dp[i][j - 1]; var curr = new pair(GFG.countTwos(mat[i][j]), GFG.countFives(mat[i][j])); top = GFG.add(top, curr); left = GFG.add(left, curr); // If there are more number // of 0s from top or left if (GFG.check(top, left)) { dp[i][j] = top; } else { dp[i][j] = left; } } } // Print the no of zeros // min(no of 2's, no of 5's) document.write(Math.min(dp[n - 1][m - 1].x,dp[n - 1][m - 1].y)); } // Function to calculate no of zeros static check(one, two) { var top = Math.min(one.x,one.y); var left = Math.min(two.x,two.y); if (top > left) { return true; } else { return false; } } // Function to calculate no of 2's static countTwos(num) { var count = 0; while (num != 0 && num % 2 == 0) { num /= 2; count++; } // Return the final count return count; } // Function to calculate no of 5's static countFives(num) { var count = 0; while (num != 0 && num % 5 == 0) { num /= 5; count++; } // Return the final count return count; } // Function to add pairs static add(one, two) { var np = new pair(one.x + two.x, one.y + two.y); // Return the resultant pair return np; } // Driver Code static main(args) { // Given N & M var N = 3; var M = 4; // Given matrix var mat = [[6, 25, 4, 10], [12, 25, 1, 15], [7, 15, 15, 5]]; // Function Call GFG.maxZeros(mat, N, M); }}GFG.main([]);</script> |
C++
// C++ program for the above approach#include <iostream>#include <utility>using namespace std;// Create a class pair to store// count of 2's and 5'sclass Pair {public: int x, y; Pair() : x(0) , y(0) { } // Parameterized Constructor Pair(int x, int y) { this->x = x; this->y = y; } // Function to convert into Strings string toString() { return "(" + to_string(this->x) + ", " + to_string(this->y) + ")"; }};// Function to calculate no of zerosbool check(Pair one, Pair two){ int top = min(one.x, one.y); int left = min(two.x, two.y); return top > left;}// Function to calculate no of 2'sint countTwos(int num){ int count = 0; while (num != 0 && num % 2 == 0) { num /= 2; count++; } // Return the final count return count;}// Function to calculate no of 5'sint countFives(int num){ int count = 0; while (num != 0 && num % 5 == 0) { num /= 5; count++; } // Return the final count return count;}// Function to add pairsPair add(Pair one, Pair two){ Pair np(one.x + two.x, one.y + two.y); // Return the resultant pair return np;}// Function to get maximum no of// zeros in product of path from// topleft to bottom rightvoid maxZeros(int mat[][4], int n, int m){ // base case if (n == 0 || m == 0) return; // Store the maximum count of // zeros till ith and jth index Pair dp[n + 1][m + 1]; // Initialize the (0, 0) dp[0][0] = Pair(countTwos(mat[0][0]), countFives(mat[0][0])); // Initialize the first row // and column explicitly for (int i = 1; i < n; i++) dp[i][0] = add(dp[i - 1][0], Pair(countTwos(mat[i][0]), countFives(mat[i][0]))); for (int i = 1; i < m; i++) dp[0][i] = add(dp[0][i - 1], Pair(countTwos(mat[0][i]), countFives(mat[0][i]))); // Iterate through all the cells for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { // Get the pair from the // top and from left Pair top = dp[i - 1][j]; Pair left = dp[i][j - 1]; Pair curr(countTwos(mat[i][j]), countFives(mat[i][j])); top = add(top, curr); left = add(left, curr); // If there are more number // of 0s from top or left if (check(top, left)) dp[i][j] = top; else dp[i][j] = left; } } // Print the no of zeros // min(no of 2's, no of 5's) cout << min(dp[n - 1][m - 1].x, dp[n - 1][m - 1].y) << endl;}int main(){ // Given N & M int N = 3, M = 4; // Given matrix int mat[][4] = { { 6, 25, 4, 10 }, { 12, 25, 1, 15 }, { 7, 15, 15, 5 } }; // Function Call maxZeros(mat, N, M); return 0;}// contributed by sdeadityasharma |
Output
4
Time Complexity: O(N*M*log10(maxE)), where maxE is the maximum value in the given matrix.
Auxiliary Space: O(N*M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
