In [185]:
"""
Need to calculate the number of 2s and 5s in the grid because that leads to number of trailing zeros.
Using DP so that same path is not calculated multiple number of times
min num of 2/5 will be current factors plus min of previous row or previous column
min_zeros is the main function
min_trail_zeros is the main logic
"""
Out[185]:
In [5]:
import numpy as np
In [83]:
m, n = map(int, input().strip().split())
In [84]:
grid = []
for i in range(m):
row = list(map(int, input().strip().split()))
assert(len(row) == n)
grid.append(row)
grid = np.array(grid)
In [98]:
grid
Out[98]:
In [129]:
m = 3
n = 3
grid1 = np.array(
[
[10, 12, 14],
[15, 30, 16],
[12, 10, 20]
]
)
In [85]:
def count_factor(num):
count = [0, 0]
factor = [2, 5]
for i in range(len(factor)):
while num % factor[i] == 0:
count[i] += 1
num = int(num/factor[i])
return count
In [158]:
def min_zero_path(tuple_1, tuple_2):
zeros_1 = min(tuple_1)
zeros_2 = min(tuple_2)
min_2 = tuple_1[0] if (tuple_1[0] < tuple_2[0]) else tuple_2[0]
min_5 = tuple_1[1] if (tuple_1[1] < tuple_2[1]) else tuple_2[1]
return min_2, min_5
In [87]:
def sum_tuples(tuple1, tuple2):
return tuple1[0] + tuple2[0], tuple1[1] + tuple2[1]
In [88]:
# def min_grid_zeros(grid, i, j, twos, fives):
# if i >= grid.shape[0] j >= grid.shape[1]:
# return twos, fives
# else:
# twos, fives = twos + count_factor(grid[i, j], 2), fives + count_factor(grid[i, j], 5)
# print(twos, fives, i, j)
# twos_r, fives_r = min_grid_zeros(grid, i, j+1, twos, fives)
# zeros_r = min(twos_r, fives_r)
# twos_d, fives_d = min_grid_zeros(grid, i+1, j, twos, fives)
# zeros_d = min(twos_d, fives_d)
# if zeros_d < zeros_r:
# return twos_d, fives_d
# else:
# return twos_r, fives_r
In [92]:
# def min_grid_zeros(grid, i, j, m, n, twos, fives):
# print(i, j)
# if i == m-1 and j == n-1:
# return count_factor(grid[i, j])
# elif i == m - 1:
# return sum_tuples(count_factor(grid[i, j]), min_grid_zeros(grid, i, j+1, m, n , twos, fives))
# elif j == n - 1:
# return sum_tuples(count_factor(grid[i, j]), min_grid_zeros(grid, i+1, j, m, n , twos, fives))
# else:
# return min_zero_path(
# sum_tuples(count_factor(grid[i, j]), min_grid_zeros(grid, i+1, j, m, n , twos, fives)),
# sum_tuples(count_factor(grid[i, j]), min_grid_zeros(grid, i, j+1, m, n , twos, fives))
# )
In [93]:
# def res_min_grid_zeros(grid):
# return min(min_grid_zeros(grid, 0, 0, grid.shape[0], grid.shape[1], 0 , 0))
In [100]:
# res_min_grid_zeros(grid1)
Out[100]:
In [159]:
def min_trail_zeros(grid):
m, n = grid.shape
t2s = np.zeros((m,n))
t5s = np.zeros((m,n))
twos, fives = count_factor(grid[0, 0])
t2s[0, 0] = twos
t5s[0, 0] = fives
for j in range(1, n):
t2s[0, j], t5s[0, j] = sum_tuples((t2s[0, j-1], t5s[0, j-1]), count_factor(grid[0, j]))
for i in range(1, m):
t2s[i, 0], t5s[i, 0] = sum_tuples((t2s[i-1, 0], t5s[i-1, 0]), count_factor(grid[i, 0]))
for i in range(1, m):
for j in range(1, n):
temp = count_factor(grid[i, j])
t2s[i, j], t5s[i, j] = min_zero_path(
sum_tuples((t2s[i-1, j], t5s[i-1, j]), temp),
sum_tuples((t2s[i, j-1], t5s[i, j-1]), temp)
)
return t2s, t5s
In [171]:
t, f = min_trail_zeros(grid)
In [182]:
def min_zeros(grid):
t, f = min_trail_zeros(grid)
m, n = grid.shape
return int(min(t[m-1, n-1], f[m-1, n-1]))
In [184]:
min_zeros(grid1)
Out[184]:
In [175]:
import pandas as pd
x = pd.DataFrame(grid)
In [176]:
x
Out[176]:
In [180]:
y = pd.DataFrame(t)
y
Out[180]:
In [181]:
z = pd.DataFrame(f)
z
Out[181]:
In [ ]: