class Solution {
public:
int maxTrailingZeros(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
// leftPrefix2[i][j] := the number of 2 in grid[i][0..j]
// leftPrefix5[i][j] := the number of 5 in grid[i][0..j]
// topPrefix2[i][j] := the number of 2 in grid[0..i][j]
// topPrefix5[i][j] := the number of 5 in grid[0..i][j]
vector<vector<int>> leftPrefix2(m, vector<int>(n));
vector<vector<int>> leftPrefix5(m, vector<int>(n));
vector<vector<int>> topPrefix2(m, vector<int>(n));
vector<vector<int>> topPrefix5(m, vector<int>(n));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
leftPrefix2[i][j] = getCount(grid[i][j], 2);
leftPrefix5[i][j] = getCount(grid[i][j], 5);
if (j > 0) {
leftPrefix2[i][j] += leftPrefix2[i][j - 1];
leftPrefix5[i][j] += leftPrefix5[i][j - 1];
}
}
for (int j = 0; j < n; ++j)
for (int i = 0; i < m; ++i) {
topPrefix2[i][j] = getCount(grid[i][j], 2);
topPrefix5[i][j] = getCount(grid[i][j], 5);
if (i > 0) {
topPrefix2[i][j] += topPrefix2[i - 1][j];
topPrefix5[i][j] += topPrefix5[i - 1][j];
}
}
int ans = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
const int curr2 = getCount(grid[i][j], 2);
const int curr5 = getCount(grid[i][j], 5);
const int l2 = leftPrefix2[i][j];
const int l5 = leftPrefix5[i][j];
const int r2 = leftPrefix2[i][n - 1] - (j ? leftPrefix2[i][j - 1] : 0);
const int r5 = leftPrefix5[i][n - 1] - (j ? leftPrefix5[i][j - 1] : 0);
const int t2 = topPrefix2[i][j];
const int t5 = topPrefix5[i][j];
const int d2 = topPrefix2[m - 1][j] - (i ? topPrefix2[i - 1][j] : 0);
const int d5 = topPrefix5[m - 1][j] - (i ? topPrefix5[i - 1][j] : 0);
ans = max({ans, min(l2 + t2 - curr2, l5 + t5 - curr5),
min(r2 + t2 - curr2, r5 + t5 - curr5),
min(l2 + d2 - curr2, l5 + d5 - curr5),
min(r2 + d2 - curr2, r5 + d5 - curr5)});
}
return ans;
}
private:
int getCount(int num, int factor) {
int count = 0;
while (num % factor == 0) {
num /= factor;
++count;
}
return count;
}
};