#2245
Maximum Trailing Zeros in a Cornered Path
expert · 1100 · lc medium +32 · verified · 37.5% accepted · 202 likes · top 16%
Description
You are given a 2D integer array grid of size m x n where every cell holds a positive integer.
A cornered path is a connected sequence of cells with at most one turn: it moves exclusively in one direction up to the turn, then exclusively in the perpendicular direction, without revisiting any cell.
The product of a path is the product of all cell values it passes through.
Return the maximum count of trailing zeros in the product of any cornered path in grid.
Note:
- Horizontal movement goes left or right.
- Vertical movement goes up or down.
Example 1:
Input: grid = [[23,17,15,3,20],[8,1,20,27,11],[9,4,6,2,21],[40,9,1,10,6],[22,7,4,5,3]]
Output: 3
Explanation: The grid on the left shows a valid cornered path.
It has a product of 15 * 20 * 6 * 1 * 10 = 18000 which has 3 trailing zeros.
It can be shown that this is the maximum trailing zeros in the product of a cornered path.
Example 2:
The grid in the middle is not a cornered path as it has more than one turn.
The grid on the right is not a cornered path as it requires a return to a previously visited cell.
Example 3:
Input: grid = [[4,3,2],[7,6,1],[8,8,8]]
Output: 0
Explanation: The grid is shown in the figure above.
There are no cornered paths in the grid that result in a product with a trailing zero.
Code
1
2
3