Prefix Sum | JAVA | O(MN) | Beat 100%
\nclass Solution {\n    public int maxTrailingZeros(int[][] grid) {\n        // find path with most matching 5 & 2 divisor\n        int m = grid.length;\n      
```\nclass Solution {\n    public int maxTrailingZeros(int[][] grid) {\n        // find path with most matching 5 & 2 divisor\n        int m = grid.length;\n        int n = grid[0].length;\n        \n        Node[][] rows = new Node[m][n];\n        Node[][] cols = new Node[m][n];\n        \n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                int five = getFive(grid[i][j]);\n                int two = getTwo(grid[i][j]);\n                Node nodeR = new Node(five, two);\n                Node nodeC = new Node(five, two);\n                \n                if (i > 0) {\n                    nodeC.five = nodeC.five + cols[i - 1][j].five;\n                    nodeC.two = nodeC.two + cols[i - 1][j].two;\n                }\n                \n                cols[i][j] = nodeC;\n                \n                if (j > 0) {\n                    nodeR.five = nodeR.five + rows[i][j - 1].five;\n                    nodeR.two = nodeR.two + rows[i][j - 1].two;\n                }\n                \n                rows[i][j] = nodeR;\n            }\n        }\n        \n        int max = 0;\n        \n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                int rowLeft5 = j - 1 < 0 ? 0 : rows[i][j - 1].five;\n                int rowLeft2 = j - 1 < 0 ? 0 : rows[i][j - 1].two;\n                int rowRight5 = rows[i][n - 1].five - rows[i][j].five;\n                int rowRight2 = rows[i][n - 1].two - rows[i][j].two;\n                \n                int colUp5 = i - 1 < 0 ? 0 : cols[i - 1][j].five;\n                int colUp2 = i - 1 < 0 ? 0 : cols[i - 1][j].two;\n                int colDown5 = cols[m - 1][j].five - cols[i][j].five;\n                int colDown2 = cols[m - 1][j].two - cols[i][j].two;\n                \n                int cur = grid[i][j];\n                \n                max = Math.max(max, Math.min(rowLeft5 + colUp5 + getFive(cur), rowLeft2 + colUp2 + getTwo(cur)));\n                max = Math.max(max, Math.min(rowLeft5 + colDown5 + getFive(cur), rowLeft2 + colDown2 + getTwo(cur)));\n                max = Math.max(max, Math.min(rowRight5 + colUp5 + getFive(cur), rowRight2 + colUp2 + getTwo(cur)));\n                max = Math.max(max, Math.min(rowRight5 + colDown5 + getFive(cur), rowRight2 + colDown2 + getTwo(cur)));\n            }\n        }\n        \n        return max;\n    }\n    \n    private int getTwo(int x) {\n        int res = 0;\n        \n        while (x % 2 == 0) {\n            res++;\n            x /= 2;\n        }\n        return res;\n    }\n    \n    private int getFive(int x) {\n        int res = 0;\n        \n        while (x % 5 == 0) {\n            res++;\n            x /= 5;\n        }\n        return res;\n    }\n}\n\nclass Node {\n    int five;\n    int two;\n    \n    public Node(int five, int two) {\n        this.five = five;\n        this.two = two;\n    }\n}\n```
['Java']