this took me 1.5 effin hours
Intuition\n Describe your first thoughts on how to solve this problem. \nUnderstand the basics: for a number to have a trailing zero, it must have a factor of 1
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUnderstand the basics: for a number to have a trailing zero, it must have a factor of 10 - a factor of 2 and a factor of 5.\nso to have n number of trailing zeroes- we must have n factors of 2 (minimum) and n factors of 5(minimum).\n\nmaybe try this one first: https://leetcode.com/problems/factorial-trailing-zeroes/description/\n\nto have maximum number of trailing zeroes, we must maximise the common factors of 2 and 5 in the total product of the path.\nie, we must maximise min(factors of 2, factors of 5);\n\npath recognition: it is given that we must only change the course (horizontal or vertical) of the path ONCE, so there will be at most ONE point in the matrix where the course of the direction will be changed.\nThe rest of the approach is brute force based upon this deduction only - but it going to be implementation heavy.\n\nFor each cell in the grid we must calculate 4 paths originating from this cell:\npath 1: turning left\npath 2: turning right\npath 3: turning up\npath 4: turning down\n\nand if the corresponding cell is the pivot cell ie, the cell where it changes course, it will have 4 possible combinations of the path.\n\n1 up-left\n2 up-right\n3 down-left\n4 down-right\n\nto calculate TOTAL factors of 2 and 5 on these paths I have used prefix sum and 4 sweeps (whew)\nI have also written functions to calculate the contribution of 2 and 5 in the number (number of factors) which is basic math, although to optimise i have used a dp array to avoid recomputation.\n\nThe Custom class was made to try to simplify the data structure we are introducing for our prefix sum of factors of 2 and 5- which is a 2D grid of pairs containing .first as number of factors of 2 and .second as number of factors of 5\n\nat the end we have considered all the possibilities and returned answer\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Custom{\npublic:\n    vector<vector <vector <pair <int, int>>>> vec;\n    Custom(int m, int n){\n        vec.resize(m, vector <vector <pair <int, int>>>(n, vector <pair <int, int>> (4)));\n    }\n};\n\nclass Solution {\nprivate:\n    int dp2[1001];\n    int dp5[1001];\n\n    int contri2(int num) {\n        if (num == 1 || num % 2 != 0) return 0;\n        if (dp2[num] != -1) return dp2[num];\n        return dp2[num] = 1 + contri2(num / 2);\n    }\n\n    int contri5(int num) {\n        if (num == 1 || num % 5 != 0) return 0;\n        if (dp5[num] != -1) return dp5[num];\n        return dp5[num] = 1 + contri5(num / 5);\n    }\npublic:\n    int maxTrailingZeros(vector<vector<int>>& grid) {\n        int m = grid.size();\n        int n = grid[0].size();\n        memset(dp2, -1, sizeof dp2);\n        memset(dp5, -1, sizeof dp5);\n\n        Custom ds(m, n);\n\n        //left sweep\n        for(int i=0; i<m; i++){\n            int curr2 = 0;\n            int curr5 = 0;\n            for(int j=0; j<n; j++){\n                int cell = grid[i][j];\n                curr2 += contri2(cell);\n                curr5 += contri5(cell);\n\n                ds.vec[i][j][0].first = curr2;\n                ds.vec[i][j][0].second = curr5;\n            }\n        }\n\n        //right sweep\n        for(int i=0; i<m; i++){\n            int curr2 = 0;\n            int curr5 = 0;\n            for(int j=n-1; j>=0; j--){\n                int cell = grid[i][j];\n                curr2 += contri2(cell);\n                curr5 += contri5(cell);\n\n                ds.vec[i][j][1].first = curr2;\n                ds.vec[i][j][1].second = curr5;\n            }\n        }\n\n        //top sweep\n        for(int i=0; i<n; i++){\n            int curr2 = 0;\n            int curr5 = 0;\n            for(int j=0; j<m; j++){\n                int cell = grid[j][i];\n                curr2 += contri2(cell);\n                curr5 += contri5(cell);\n\n                ds.vec[j][i][2].first = curr2;\n                ds.vec[j][i][2].second = curr5;\n            }\n        }\n\n        //bottom sweep\n        for(int i=0; i<n; i++){\n            int curr2 = 0;\n            int curr5 = 0;\n            for(int j=m-1; j>=0; j--){\n                int cell = grid[j][i];\n                curr2 += contri2(cell);\n                curr5 += contri5(cell);\n\n                ds.vec[j][i][3].first = curr2;\n                ds.vec[j][i][3].second = curr5;\n            }\n        }\n\n        int ans = INT_MIN;\n        for(int i=0; i<m; i++){\n            for(int j=0; j<n; j++){\n                int cell = grid[i][j];\n                int c2 = contri2(cell);\n                int c5 = contri5(cell);\n                int poss1 = min(ds.vec[i][j][2].first+ds.vec[i][j][0].first - c2,\n                                ds.vec[i][j][2].second+ds.vec[i][j][0].second -c5);\n                int poss2 = min(ds.vec[i][j][2].first+ds.vec[i][j][1].first-c2,\n                                ds.vec[i][j][2].second+ds.vec[i][j][1].second-c5);\n                int poss3 = min(ds.vec[i][j][3].first+ds.vec[i][j][0].first-c2,\n                                ds.vec[i][j][3].second+ds.vec[i][j][0].second-c5);\n                int poss4 = min(ds.vec[i][j][3].first+ds.vec[i][j][1].first-c2,\n                                ds.vec[i][j][3].second+ds.vec[i][j][1].second-c5);\n\n                ans = max({ans, poss1, poss2, poss3, poss4});\n            }\n        }\n\n        return ans;\n    }\n};\n```
['Array', 'Math', 'Dynamic Programming', 'Matrix', 'Prefix Sum', 'C++']