[Python] Self-explain code using Prefix sum
Intuition\nSince product of numbers and its trailing zeros will never go down with additional numbers. The problem becomes "for each point (i,j) in the grid, co
# Intuition\nSince product of numbers and its trailing zeros will never go down with additional numbers. The problem becomes "**for each point (i,j) in the grid, compute the max trailling zeros of product of 4 L-shape pathes(till boundary). Then find the max num of trailling zeros over all points**" That\'s definately a  prefix sum problem.\n\n# Approach\nTrailing zeros can be calculated by the min count of factor 2 and factor 5. Hence, we can maintain a tup of counts of factor 2 and factor 5 and calculate prefix sum. Than scan over the grid, ultilize the prefix sums to get the max.\n\nThe code below create a class for demostration(though slow down the caculation). It also minimize the memory needed to hold prefix sum. Other parts are self-explianed.\n\n# Complexity\n- Time complexity: O(mn)\n\n- Space complexity: O(n)\n (Ignore the ngrid which cab be transferred on the fly)\n\n# Code\n```\nclass Solution:\n    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n        class BaseTup:\n            def __init__(self, a=0, b=0):\n                self.a, self.b = a, b\n\n            @classmethod\n            def from_num(cls, n): \n                c2 = c5 = 0\n                while n and n%2==0:\n                    c2 += 1\n                    n = n>>1\n                while n and n%5==0:\n                    c5 += 1\n                    n //= 5\n                return BaseTup(c2, c5)\n\n            @classmethod\n            def sum(cls, iterable):\n                return sum(iterable, start = BaseTup())\n\n            def __add__(self, o):\n                return BaseTup(self.a + o.a, self.b + o.b)\n\n            def __sub__(self, o):\n                return BaseTup(self.a - o.a, self.b - o.b)\n\n            @property\n            def trail_zeros(self):\n                return min(self.a, self.b)\n\n        \n        m,n = len(grid), len(grid[0])\n        ngrid = [[ BaseTup.from_num(grid[i][j]) for j in range(n)] for i in range(m)]\n\n        up_sum = [BaseTup() for _ in range(n)]\n        down_sum = [BaseTup.sum(ngrid[i][j] for i in range(m)) for j in range(n)]\n\n        zmax = 0\n        for i in range(m):\n            rsum = BaseTup.sum(ngrid[i])\n            lsum = BaseTup()\n            for j in range(n):\n                t = ngrid[i][j]\n                lsum += t\n                down_sum[j] -= t\n\n                zmax = max(zmax, \n                    (lsum+up_sum[j]).trail_zeros,\n                    (rsum+up_sum[j]).trail_zeros,\n                    (lsum+down_sum[j]).trail_zeros,\n                    (rsum+down_sum[j]).trail_zeros)\n\n                rsum -= t\n                up_sum[j] += t\n                \n        return zmax\n\n```
['Python3']