import numpy as np

class Solution:
    def maxTrailingZeros(self, grid: List[List[int]]) -> int:
        A = np.array(grid)
        def cumdivs(d):
            D = sum(A % d**i == 0 for i in range(1, 10))
            return D.cumsum(0) + D.cumsum(1) - D
        return max(np.minimum(cumdivs(2), cumdivs(5)).max()
                   for _ in range(4)
                   if [A := np.rot90(A)])
class Solution {
    public int maxTrailingZeros(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][][] dph = new int[m][n][3];
        int[][][] dpv = new int[m][n][3];
        int hmax0 = 0;
        int vmax0 = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int curr = grid[i][j];
                int two = 0;
                int five = 0;
                if (j >= 1) {
                    two = dph[i][j-1][1];
                    five = dph[i][j-1][2];
                }
                while (curr > 0 && curr % 2 == 0) {
                    two++;
                    curr /= 2;
                }
                while (curr > 0 && curr % 5 == 0) {
                    five++;
                    curr /= 5;
                }
                dph[i][j][1] = two;
                dph[i][j][2] = five;
                dph[i][j][0] = Math.min(dph[i][j][1], dph[i][j][2]);
            }
            hmax0 = Math.max(hmax0, dph[i][n-1][0]);
        }
        
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                int curr = grid[i][j];
                int two = 0;
                int five = 0;
                if (i >= 1) {
                    two = dpv[i-1][j][1];
                    five = dpv[i-1][j][2];
                }
                while (curr > 0 && curr % 2 == 0) {
                    two++;
                    curr /= 2;
                }
                while (curr > 0 && curr % 5 == 0) {
                    five++;
                    curr /= 5;
                }
                dpv[i][j][1] = two;
                dpv[i][j][2] = five;
                dpv[i][j][0] = Math.min(dpv[i][j][1], dpv[i][j][2]);
            }
            vmax0 = Math.max(vmax0, dpv[m-1][j][0]);
        }
		
        int res = Math.max(vmax0, hmax0);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int otwo = dph[i][j][1];
                int ofive = dph[i][j][2];
                
                int res1 = 0;
                if (i >= 1) {
                    int ntwo = otwo + dpv[i-1][j][1];
                    int nfive = ofive + dpv[i-1][j][2];
                    res1 = Math.min(ntwo, nfive);
                }
                
                int res2 = 0;
                if (i < m - 1) {
                    int ntwo = otwo + dpv[m-1][j][1] - dpv[i][j][1];
                    int nfive = ofive + dpv[m-1][j][2] - dpv[i][j][2];
                    res2 = Math.min(ntwo, nfive);
                }
                res = Math.max(res, res1);
                res = Math.max(res, res2);
            }
			
			for (int j = n - 1; j >= 0; j--) {
                int otwo = 0;
                int ofive = 0;
                if (j >= 1) {
                    otwo = dph[i][n-1][1] - dph[i][j-1][1];
                    ofive = dph[i][n-1][2] - dph[i][j-1][2];
                } else {
                    otwo = dph[i][n-1][1];
                    ofive = dph[i][n-1][2];
                }
                
                int res1 = 0;
                if (i >= 1) {
                    int ntwo = otwo + dpv[i-1][j][1];
                    int nfive = ofive + dpv[i-1][j][2];
                    res1 = Math.min(ntwo, nfive);
                }
                
                int res2 = 0;
                if (i < m - 1) {
                    int ntwo = otwo + dpv[m-1][j][1] - dpv[i][j][1];
                    int nfive = ofive + dpv[m-1][j][2] - dpv[i][j][2];
                    res2 = Math.min(ntwo, nfive);
                }
                
                res = Math.max(res, res1);
                res = Math.max(res, res2);
            }
        }
		
        return res;
    }
}
Maximum Trailing Zeros in a Cornered Path
You are given a 2D integer array grid of size m x n, where each cell contains a positive integer.

A cornered path is defined as a set of adjacent cells with at most one turn. More specifically, the path should exclusively move either horizontally or vertically up to the turn (if there is one), without returning to a previously visited cell. After the turn, the path will then move exclusively in the alternate direction: move vertically if it moved horizontally, and vice versa, also without returning to a previously visited cell.

The product of a path is defined as the product of all the values in the path.

Return the maximum number of trailing zeros in the product of a cornered path found in grid.

Note:


	Horizontal movement means moving in either the left or right direction.
	Vertical movement means moving in either the up or down direction.


&nbsp;
Example 1:

Input: grid = [[23,17,15,3,20],[8,1,20,27,11],[9,4,6,2,21],[40,9,1,10,6],[22,7,4,5,3]]
Output: 3
Explanation: The grid on the left shows a valid cornered path.
It has a product of 15 * 20 * 6 * 1 * 10 = 18000 which has 3 trailing zeros.
It can be shown that this is the maximum trailing zeros in the product of a cornered path.

The grid in the middle is not a cornered path as it has more than one turn.
The grid on the right is not a cornered path as it requires a return to a previously visited cell.


Example 2:

Input: grid = [[4,3,2],[7,6,1],[8,8,8]]
Output: 0
Explanation: The grid is shown in the figure above.
There are no cornered paths in the grid that result in a product with a trailing zero.


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 105
	1 &lt;= m * n &lt;= 105
	1 &lt;= grid[i][j] &lt;= 1000


var maxTrailingZeros = function(grid) {
    const m = grid.length;
    const n = grid[0].length;

    const postfixCols = [];

    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            const num = grid[i][j];

            if (postfixCols[j] == null) postfixCols[j] = { 2: 0, 5: 0 };

            postfixCols[j]["2"] += getCount(num, 2);
            postfixCols[j]["5"] += getCount(num, 5);
        }
    }

    const prefixCols = [];

    for (let j = 0; j < n; ++j) {
        prefixCols[j] = { 0: 0, 2: 0, 5: 0 };
    }

    let maxZeros = 0;

    for (let i = 0; i < m; ++i) {
        const postfixRow = { 0: 0, 2: 0, 5: 0 };

        for (let j = n - 1; j >= 0; --j) {
            const num = grid[i][j];

            postfixRow["2"] += getCount(num, 2);
            postfixRow["5"] += getCount(num, 5);
        }

        let prefixRow = { 0: 0, 2: 0, 5: 0 };

        for (let j = 0; j < n; ++j) {
            const num = grid[i][j];

            const twoCount = getCount(num, 2);
            const fiveCount = getCount(num, 5);

            postfixRow["2"] -= twoCount;
            postfixCols[j]["2"] -= twoCount;

            postfixRow["5"] -= fiveCount;
            postfixCols[j]["5"] -= fiveCount;

            // down-right => prefixCol + postfixRow
            const downRight = calculateTrailingZeros(prefixCols[j], postfixRow, num);
            // down-left => prefixCol + prefixRow
            const downLeft = calculateTrailingZeros(prefixCols[j], prefixRow, num);
            // up-right => postfixCols + postfixRow
            const upRight = calculateTrailingZeros(postfixCols[j], postfixRow, num);
            // up-left => postfixCols + prefixRow
            const upLeft = calculateTrailingZeros(postfixCols[j], prefixRow, num);

            maxZeros = Math.max(maxZeros, downRight, downLeft, upRight, upLeft);

            prefixRow["2"] += twoCount;
            prefixCols[j]["2"] += twoCount;

            prefixRow["5"] += fiveCount;
            prefixCols[j]["5"] += fiveCount;
        }
    }

    return maxZeros;

    function calculateTrailingZeros(col, row, currNum) {
        let twosCount = 0;
        let fivesCount = 0;
        let zerosCount = 0;

        twosCount = row["2"] + col["2"];
        fivesCount = row["5"] + col["5"];

        twosCount += getCount(currNum, 2);
        fivesCount += getCount(currNum, 5);
        return Math.min(twosCount, fivesCount);
    }

    function getCount(num, divisor) {
        let count = 0;

        while (num % divisor === 0) {
            ++count;
            num /= divisor;
        }

        return count;
    }
};
array<int, 2> operator+(const array<int, 2> &l, const array<int, 2> &r) { return { l[0] + r[0], l[1] + r[1] }; }
array<int, 2> operator-(const array<int, 2> &l, const array<int, 2> &r) { return { l[0] - r[0], l[1] - r[1] }; }
int pairs(const array<int, 2> &p) { return min(p[0], p[1]); }

class Solution {
public:
int factors(int i, int f) {
    return i % f ? 0 : 1 + factors(i / f, f);
}
int maxTrailingZeros(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size(), res = 0;
    vector<vector<array<int, 2>>> h(m, vector<array<int, 2>>(n + 1)), v(m + 1, vector<array<int, 2>>(n));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) {
            array<int, 2> f25 = { factors(grid[i][j], 2), factors(grid[i][j], 5) };
            v[i + 1][j] = v[i][j] + f25;
            h[i][j + 1] = h[i][j] + f25;
        }
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) {
            auto v1 = v[i + 1][j], v2 = v[m][j] - v[i][j];
            auto h1 = h[i][j], h2 = h[i][n] - h[i][j + 1];
            res = max({res, pairs(v1 + h1), pairs(v1 + h2), pairs(v2 + h1), pairs(v2 + h2)});
        }
    return res;
}
};