Maximum Trailing Zeros in a Cornered Path

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from typing import List

class Solution:
    def factors(self, i: int, f: int) -> int:
        return 0 if i % f else 1 + self.factors(i // f, f)

    def pairs(self, p) -> int:
        return min(p[0], p[1])

    def maxTrailingZeros(self, grid: List[List[int]]) -> int:
        m, n, res = len(grid), len(grid[0]), 0
        h = [[(0, 0)] * (n + 1) for _ in range(m)]
        v = [[(0, 0)] * n for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                f25 = (self.factors(grid[i][j], 2), self.factors(grid[i][j], 5))
                v[i + 1][j] = (v[i][j][0] + f25[0], v[i][j][1] + f25[1])
                h[i][j + 1] = (h[i][j][0] + f25[0], h[i][j][1] + f25[1])
        for i in range(m):
            for j in range(n):
                v1, v2 = v[i + 1][j], (v[m][j][0] - v[i][j][0], v[m][j][1] - v[i][j][1])
                h1, h2 = h[i][j], (h[i][n][0] - h[i][j + 1][0], h[i][n][1] - h[i][j + 1][1])
                res = max(res, self.pairs((v1[0] + h1[0], v1[1] + h1[1])), self.pairs((v1[0] + h2[0], v1[1] + h2[1])),
                          self.pairs((v2[0] + h1[0], v2[1] + h1[1])), self.pairs((v2[0] + h2[0], v2[1] + h2[1])))
        return res