Dada una array mat[][] de dimensiones N * M ,
la tarea es imprimir el número máximo de ceros finales que se pueden obtener en el producto de los elementos de la array en el camino desde la celda superior izquierda (0, 0) hasta la celda inferior derecha (N – 1, M – 1) de la array dada. Los únicos movimientos posibles desde cualquier celda (i, j) son (i + 1, j) o (i, j + 1).
Ejemplos:
Entrada: N = 3, M = 4, mat[][] = {{6, 25, 4, 10}, {12, 25, 1, 15}, {7, 15, 15, 5}}
Salida: 4
Explicación: entre todos los caminos posibles desde la parte superior izquierda hasta la parte inferior derecha, el camino (6, 25, 4, 10, 15, 5} tiene un producto (= 450000) con un número máximo de ceros finales. Por lo tanto, la cuenta de ceros es 4.Entrada: N = 3, M = 3, mat[][] = {{2, 5, 2}, {10, 2, 40}, {5, 4, 8}}
Salida: 2
Enfoque ingenuo: la idea es generar todos los caminos posibles desde la celda superior izquierda (0, 0) hasta la celda inferior derecha (N – 1, M – 1) de la array dada recursivamente y calcular el producto de los elementos en cada uno . sendero. Imprime el número máximo de ceros finales entre los productos. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos producto para almacenar el producto de todos los elementos posibles en la ruta desde la celda superior izquierda (0, 0) hasta la celda inferior derecha (N – 1, M – 1) .
- La siguiente relación de recurrencia calcula el valor maxZeros de todas las rutas posibles desde la celda superior izquierda (0, 0) hasta la celda inferior derecha (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]))
donde ,
maxZeros() es la función que devuelve el número máximo de ceros finales.
- A partir de la relación de recurrencia anterior, genere todos los caminos posibles recursivamente y cuando cualquier camino llegue a la celda (N – 1, M – 1) , luego encuentre el recuento de ceros finales del producto hasta ese camino.
- Cuando finalice cada llamada recursiva, maximice el recuento de ceros devueltos por esas llamadas recursivas.
- Imprima el número máximo de ceros finales después de los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
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 zeros
int zeros = 0;
// Function that counts the trailing
// zeros in the given number num
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 count maximum trailing
// zeros in product of elements in a
// path from top-left to bottom-right
void 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 obtained
void 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 Code
int 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 approach
import 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 approach N = 3 M = 4 # Stores the maximum count # of zeros zeros = 0 # Function that counts the # trailing zeros in the # given number num def 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-right def 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 obtained def maxZerosUtil(mat, i, j, product): # Function Call maxZeros(mat, 0, 0, 1) # Print the maximum # count print(zeros) # Driver Code if __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 approach
using System;
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,
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 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,
int N, int M)
{
// Function Call
maxZeros(mat, 0, 0, 1, N, M);
// Print the maximum count
Console.WriteLine(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, N, M);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
var N = 3
var M = 4
// Stores the maximum count of zeros
var zeros = 0;
// Function that counts the trailing
// zeros in the given number num
function 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-right
function 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 obtained
function maxZerosUtil(mat, i, j, product)
{
// Function Call
maxZeros(mat, 0, 0, 1);
// Print the maximum count
document.write( zeros + "<br>");
}
// Driver Code
// Given matrix
var mat = [ [ 6, 25, 4, 10 ],
[ 12, 25, 1, 15 ],
[ 7, 15, 15, 5 ]];
// Function Call
maxZerosUtil(mat, 0, 0, 1);
</script>
Producción
4
Complejidad de Tiempo: O(2 N*M )
Espacio Auxiliar: O(1)
Programación dinámica usando el enfoque de abajo hacia arriba :las llamadas recursivas en el enfoque anterior se pueden reducir usando una array auxiliardp[][]y calcular el valor de cada estado en el enfoque de abajo hacia arriba. Siga los pasos a continuación:
- Cree una array auxiliar dp[][] de tamaño N*M .
- dp[i][j] representa el número de cincos y doses hasta la i -ésima fila y la j -ésima columna.
- Recorra la array y actualice cada estado de la array dp[][] como:
dp[i][j] = max(dp[i – 1][j], dp[i][j – 1])
- Imprima el mínimo de la cuenta respectiva de (2 s, 5 s) después de los pasos anteriores como resultado.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
// Create a class pair to store
// count of 2's and 5's
class pair {
int x, y;
// Parameterized Constructor
pair(int x, int y)
{
this.x = x;
this.y = y;
}
// Function to covert 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);
}
}
C#
// C# program for the above approach
using System;
// Create a class pair to store
// count of 2's and 5's
public class pair
{
public int x, y;
// Parameterized Constructor
public pair(int x, int y)
{
this.x = x;
this.y = y;
}
// Function to covert 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)
Console.WriteLine(
Math.Min(dp[n - 1, m - 1].x,
dp[n - 1, m - 1].y));
}
// Function to calculate no of zeros
public 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's
public 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's
public 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 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);
}
}
// This code is contributed by Amit Katiyar
Producción
4
Complejidad de tiempo: O(N*M*log 10 (maxE)), donde maxE es el valor máximo en la array dada.
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA