prefix sums with explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nfor every point as a point of  direction change if we know the max zeros, answer is max
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nfor every point as a point of  direction change if we know the max zeros, answer is maxium of all point max zeros. a 10 can be formed with 5 and 2 only\n# Approach\n<!-- Describe your approach to solving the problem. -->\ncalculated prefix sum of 2\'s and 5\'s in each direction for every point\n\nat every point add left with up or down sums, right with up or down and take maximum for that point\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n2 * O(N)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n10 * O(N)\n# Code\n```\nclass Solution {\n    int cntFactorials(int val, int exp) {\n        int cnt = 0;\n        while(val % exp == 0) {\n            cnt++;\n            val /= exp;\n        }\n        return cnt;\n    }\n    typedef struct prefix{\n        int twos = -1;\n        int fives = -1;\n        prefix operator+(prefix b) {\n            return {twos + b.twos, fives + b.fives};\n        }\n    }prefix;\n    typedef struct elemInfo{\n        int twos = -1;\n        int fives = -1;\n        prefix left;\n        prefix right;\n        prefix up;\n        prefix down;\n    }elemInfo;\npublic:\n    int maxTrailingZeros(vector<vector<int>>& grid) {\n        vector<vector<elemInfo>> data(grid.size(), vector<elemInfo>(grid[0].size()));\n        int res = 0;\n        // calculate left and up prefix sums of 2\'s and 5\'s\n        for( int x = 0; x < grid.size() ; x++) {\n            for(int y = 0; y < grid[0].size();y++) {\n                if(data[x][y].fives == -1){\n                    data[x][y].fives = cntFactorials(grid[x][y], 5);\n                }\n                if(data[x][y].twos == -1){\n                    data[x][y].twos = cntFactorials(grid[x][y], 2);\n                }\n\n                if(y > 0)\n                    data[x][y].left = data[x][y-1].left + prefix{data[x][y].twos, data[x][y].fives};\n                else\n                    data[x][y].left = {data[x][y].twos, data[x][y].fives};\n                if(x > 0)\n                    data[x][y].up = data[x-1][y].up + prefix{data[x][y].twos, data[x][y].fives};\n                else\n                    data[x][y].up = {data[x][y].twos, data[x][y].fives};\n\n            }\n        }\n        // calculate right and  down prefix sums of 2\'s and 5\'s\n        for( int x = grid.size() - 1; x >=0 ; x--) {\n            for(int y = grid[0].size() - 1; y >=0; y--) {\n                if(x + 1 < grid.size())\n                    data[x][y].down = data[x + 1][y].down +  prefix{data[x][y].twos, data[x][y].fives};\n                else\n                    data[x][y].down =  {data[x][y].twos, data[x][y].fives};\n                if(y + 1 < grid[0].size())\n                    data[x][y].right = data[x][y+1].right +  prefix{data[x][y].twos, data[x][y].fives};\n                else\n                    data[x][y].right =  {data[x][y].twos, data[x][y].fives};\n\n\n                // now that we have count of twos and fives of current element from all direcions\n                // calculate max trailing zeros with current element as point of direction change\n                res = max(res, min(data[x][y].left.fives + data[x][y].up.fives - data[x][y].fives,\n                                             data[x][y].left.twos + data[x][y].up.twos - data[x][y].twos));\n                res = max(res, min(data[x][y].left.fives + data[x][y].down.fives - data[x][y].fives,\n                                             data[x][y].left.twos + data[x][y].down.twos - data[x][y].twos));\n                res = max(res, min(data[x][y].right.fives + data[x][y].up.fives - data[x][y].fives,\n                                             data[x][y].right.twos + data[x][y].up.twos - data[x][y].twos));\n                res = max(res, min(data[x][y].right.fives + data[x][y].down.fives - data[x][y].fives,\n                                             data[x][y].right.twos + data[x][y].down.twos - data[x][y].twos));\n            }\n        }\n        \n        // for( int x = 0; x < grid.size() ; x++) {\n        //     for(int y = 0; y < grid[0].size();y++) {\n        //         cout << data[x][y].left << " ";\n        //     }\n        //     cout <<endl;\n        // }\n        return res;\n    }\n};\n```
['C++']