Prefix Sum Approach | C++ | Comments
```\n// Approach - We know basic idea about how to form 10 i.e. 5 * 2\n// So thats it we use the same idea here we calculate 5\'s and 2\'s in division of each g
```\n// Approach - We know basic idea about how to form 10 i.e. 5 * 2\n// So thats it we use the same idea here we calculate 5\'s and 2\'s in division of each grid element \n// and maintain sum array\n\n\n// sum[n][m][2] --> 0 --> Number of 5\'s and 1 --> Number of 2\'s \n\n\n\nclass Solution {\npublic:\n\n    // Utility function to get frequency of divisor forming the number \n    int getIt(int n,int p)\n    {\n        int ans = 0;\n        while(n > 0)\n        {\n            if(n % p != 0)break;\n            ans++;\n            n/=p;\n        }\n        return ans;\n    }\n\n    int maxTrailingZeros(vector<vector<int>>& grid) {\n        int n = grid.size();\n        int m = grid[0].size();\n\n        // Row wise Prefix Sum \n        int sum[n+1][m+1][2];\n        memset(sum,0,sizeof sum);\n\n        for(int i=1;i<=n;i++)\n        {\n            for(int j=1;j<=m;j++)\n            {\n                sum[i][j][0] = getIt(grid[i-1][j-1],2);\n                sum[i][j][1] = getIt(grid[i-1][j-1],5);\n            }\n        }\n\n        for(int i=1;i<=n;i++){\n            for(int j=1;j<=m;j++)\n            {\n                sum[i][j][0] += sum[i][j-1][0];\n                sum[i][j][1] += sum[i][j-1][1];\n            }\n        }\n\n        // :------------------------------------------------->\n\n         // Column Wise Prefix Sum\n        int sum2[n+1][m+1][2];\n        memset(sum2,0,sizeof sum2);\n        \n        for(int i=1;i<=n;i++)\n        {\n            for(int j=1;j<=m;j++)\n            {\n                sum2[i][j][0] = getIt(grid[i-1][j-1],2);\n                sum2[i][j][1] = getIt(grid[i-1][j-1],5);\n            }\n        }\n\n        for(int i=1;i<=n;i++){\n            for(int j=1;j<=m;j++)\n            {\n                sum2[i][j][0] += sum2[i-1][j][0];\n                sum2[i][j][1] += sum2[i-1][j][1];\n            }\n        }\n\n\n        // :---------------------------------------------->\n\n        // Cheap Variable to Store Answer\n        int ans = 0;\n\n\n        for(int i=1;i<=n;i++)\n        {\n            for(int j=1;j<=m;j++)\n            {\n\n                // Current Grid Element\n                int x = sum[i][j][0] - sum[i][j-1][0];\n                int y = sum[i][j][1] - sum[i][j-1][1];\n\n                // Take all possible answers considering current grid element as corner\n\n                // Convention --> L1, L2,R1,R2,U1,U2,D1,D2\n                // 1 --> Number is 5\'s\n                // 2 --> Number of 2\'s\n\n                // Left\n                int L1 = sum[i][j-1][0];\n                int L2 = sum[i][j-1][1];\n\n                // Right\n                int R1 = sum[i][m][0] - sum[i][j][0];\n                int R2 = sum[i][m][1] - sum[i][j][1];\n\n                // Up\n                int U1 = sum2[i-1][j][0];\n                int U2 = sum2[i-1][j][1];\n\n                // Down\n                int D1 = sum2[n][j][0] - sum2[i][j][0];\n                int D2 = sum2[n][j][1] - sum2[i][j][1];\n\n                // Our duty to calculate max answer\n                // Max answer will be the min(No of 5\'s, No of 2\'s) in the cornered Path\n                ans = max(ans,min(L1 + x + U1, L2 + y + U2));\n                ans = max(ans,min(L1 + x + D1, L2 + y + D2));\n\n                ans = max(ans,min(R1 + x + U1, R2 + y + U2));\n                ans = max(ans,min(R1 + x + D1, R2 + y + D2));\n\n\n            }\n        }\n        \n        // Hey, We just did it, Now its time to return\n        return ans;\n        \n    }\n};
['Prefix Sum']