2245. Maximum Trailing Zeros in a Cornered Path Medium

1/**
2 * [2245] Maximum Trailing Zeros in a Cornered Path
3 *
4 * You are given a 2D integer array grid of size m x n, where each cell contains a positive integer.
5 * A cornered path is defined as a set of adjacent cells with at most one turn. More specifically, the path should exclusively move either horizontally or vertically up to the turn (if there is one), without returning to a previously visited cell. After the turn, the path will then move exclusively in the alternate direction: move vertically if it moved horizontally, and vice versa, also without returning to a previously visited cell.
6 * The product of a path is defined as the product of all the values in the path.
7 * Return the maximum number of trailing zeros in the product of a cornered path found in grid.
8 * Note:
9 *
10 * Horizontal movement means moving in either the left or right direction.
11 * Vertical movement means moving in either the up or down direction.
12 *
13 *  
14 * Example 1:
15 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/23/ex1new2.jpg" style="width: 577px; height: 190px;" />
16 * 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]]
17 * Output: 3
18 * Explanation: The grid on the left shows a valid cornered path.
19 * It has a product of 15 * 20 * 6 * 1 * 10 = 18000 which has 3 trailing zeros.
20 * It can be shown that this is the maximum trailing zeros in the product of a cornered path.
21 * The grid in the middle is not a cornered path as it has more than one turn.
22 * The grid on the right is not a cornered path as it requires a return to a previously visited cell.
23 *
24 * Example 2:
25 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/25/ex2.jpg" style="width: 150px; height: 157px;" />
26 * Input: grid = [[4,3,2],[7,6,1],[8,8,8]]
27 * Output: 0
28 * Explanation: The grid is shown in the figure above.
29 * There are no cornered paths in the grid that result in a product with a trailing zero.
30 *
31 *  
32 * Constraints:
33 *
34 * m == grid.length
35 * n == grid[i].length
36 * 1 <= m, n <= 10^5
37 * 1 <= m * n <= 10^5
38 * 1 <= grid[i][j] <= 1000
39 *
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/maximum-trailing-zeros-in-a-cornered-path/
44// discuss: https://leetcode.com/problems/maximum-trailing-zeros-in-a-cornered-path/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47use std::cmp;
48impl Solution {
49    pub fn max_trailing_zeros(grid: Vec<Vec<i32>>) -> i32 {
50        let m = grid.len();
51        let n = grid[0].len();
52        let mut down = vec![vec![(0, 0); n]; m];
53        let mut right = vec![vec![(0, 0); n]; m];
54
55        for i in 0..m {
56            for j in 0..n {
57                let t = Self::two_and_five(grid[i][j]);
58                if i == 0 && j == 0 {
59                    down[i][j] = t.clone();
60                    right[i][j] = t.clone();
61                } else if i == 0 {
62                    down[i][j] = t.clone();
63                    right[i][j] = (right[i][j - 1].0 + t.0, right[i][j - 1].1 + t.1);
64                } else if j == 0 {
65                    down[i][j] = (down[i - 1][j].0 + t.0, down[i - 1][j].1 + t.1);
66                    right[i][j] = t.clone();
67                } else {
68                    right[i][j] = (right[i][j - 1].0 + t.0, right[i][j - 1].1 + t.1);
69                    down[i][j] = (down[i - 1][j].0 + t.0, down[i - 1][j].1 + t.1);
70                }
71            }
72        }
73
74        let mut result = 0;
75        for i in 0..m {
76            for j in 0..n {
77                let x = Self::two_and_five(grid[i][j]);
78                // include i, j
79                let u = down[i][j];
80                let l = right[i][j];
81                // does not include i, j
82                let d = (
83                    down[m - 1][j].0 - down[i][j].0,
84                    down[m - 1][j].1 - down[i][j].1,
85                );
86                let r = (
87                    right[i][n - 1].0 - right[i][j].0,
88                    right[i][n - 1].1 - right[i][j].1,
89                );
90
91                result = cmp::max(result, Self::zeros(&u, &d));
92                result = cmp::max(result, Self::zeros(&u, &r));
93                result = cmp::max(result, Self::zeros(&l, &d));
94                result = cmp::max(result, Self::zeros(&l, &r));
95                result = cmp::max(result, Self::zeros(&u, &(l.0 - x.0, l.1 - x.1)));
96                result = cmp::max(result, Self::zeros(&d, &(r.0 + x.0, r.1 + x.1)));
97            }
98        }
99        result
100    }
101
102    fn zeros(a: &(i32, i32), b: &(i32, i32)) -> i32 {
103        cmp::min(a.0 + b.0, a.1 + b.1)
104    }
105
106    fn two_and_five(n: i32) -> (i32, i32) {
107        let mut remain = n;
108        let mut five = 0;
109        let mut two = 0;
110
111        while remain % 2 == 0 {
112            two += 1;
113            remain /= 2;
114        }
115
116        while remain % 5 == 0 {
117            five += 1;
118            remain /= 5;
119        }
120
121        (two, five)
122    }
123}
124
125// submission codes end
126
127#[cfg(test)]
128mod tests {
129    use super::*;
130
131    #[test]
132    fn test_2245() {
133        assert_eq!(
134            Solution::max_trailing_zeros(vec![
135                vec![23, 17, 15, 3, 20],
136                vec![8, 1, 20, 27, 11],
137                vec![9, 4, 6, 2, 21],
138                vec![40, 9, 1, 10, 6],
139                vec![22, 7, 4, 5, 3]
140            ]),
141            3
142        );
143        assert_eq!(
144            Solution::max_trailing_zeros(vec![vec![4, 3, 2], vec![7, 6, 1], vec![8, 8, 8]]),
145            0
146        );
147    }
148}
149