Skip to content

2245. Maximum Trailing Zeros in a Cornered Path 👎

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
 public:
  int maxTrailingZeros(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    // leftPrefix2[i][j] := the number of 2 in grid[i][0..j]
    // leftPrefix5[i][j] := the number of 5 in grid[i][0..j]
    // topPrefix2[i][j] := the number of 2 in grid[0..i][j]
    // topPrefix5[i][j] := the number of 5 in grid[0..i][j]
    vector<vector<int>> leftPrefix2(m, vector<int>(n));
    vector<vector<int>> leftPrefix5(m, vector<int>(n));
    vector<vector<int>> topPrefix2(m, vector<int>(n));
    vector<vector<int>> topPrefix5(m, vector<int>(n));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        leftPrefix2[i][j] = getCount(grid[i][j], 2);
        leftPrefix5[i][j] = getCount(grid[i][j], 5);
        if (j > 0) {
          leftPrefix2[i][j] += leftPrefix2[i][j - 1];
          leftPrefix5[i][j] += leftPrefix5[i][j - 1];
        }
      }

    for (int j = 0; j < n; ++j)
      for (int i = 0; i < m; ++i) {
        topPrefix2[i][j] = getCount(grid[i][j], 2);
        topPrefix5[i][j] = getCount(grid[i][j], 5);
        if (i > 0) {
          topPrefix2[i][j] += topPrefix2[i - 1][j];
          topPrefix5[i][j] += topPrefix5[i - 1][j];
        }
      }

    int ans = 0;
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        const int curr2 = getCount(grid[i][j], 2);
        const int curr5 = getCount(grid[i][j], 5);
        const int l2 = leftPrefix2[i][j];
        const int l5 = leftPrefix5[i][j];
        const int r2 = leftPrefix2[i][n - 1] - (j ? leftPrefix2[i][j - 1] : 0);
        const int r5 = leftPrefix5[i][n - 1] - (j ? leftPrefix5[i][j - 1] : 0);
        const int t2 = topPrefix2[i][j];
        const int t5 = topPrefix5[i][j];
        const int d2 = topPrefix2[m - 1][j] - (i ? topPrefix2[i - 1][j] : 0);
        const int d5 = topPrefix5[m - 1][j] - (i ? topPrefix5[i - 1][j] : 0);
        ans = max({ans, min(l2 + t2 - curr2, l5 + t5 - curr5),
                   min(r2 + t2 - curr2, r5 + t5 - curr5),
                   min(l2 + d2 - curr2, l5 + d5 - curr5),
                   min(r2 + d2 - curr2, r5 + d5 - curr5)});
      }

    return ans;
  }

 private:
  int getCount(int num, int factor) {
    int count = 0;
    while (num % factor == 0) {
      num /= factor;
      ++count;
    }
    return count;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
  public int maxTrailingZeros(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    // leftPrefix2[i][j] := the number of 2 in grid[i][0..j]
    // leftPrefix5[i][j] := the number of 5 in grid[i][0..j]
    // topPrefix2[i][j] := the number of 2 in grid[0..i][j]
    // topPrefix5[i][j] := the number of 5 in grid[0..i][j]
    int[][] leftPrefix2 = new int[m][n];
    int[][] leftPrefix5 = new int[m][n];
    int[][] topPrefix2 = new int[m][n];
    int[][] topPrefix5 = new int[m][n];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        leftPrefix2[i][j] = getCount(grid[i][j], 2);
        leftPrefix5[i][j] = getCount(grid[i][j], 5);
        if (j > 0) {
          leftPrefix2[i][j] += leftPrefix2[i][j - 1];
          leftPrefix5[i][j] += leftPrefix5[i][j - 1];
        }
      }

    for (int j = 0; j < n; ++j)
      for (int i = 0; i < m; ++i) {
        topPrefix2[i][j] = getCount(grid[i][j], 2);
        topPrefix5[i][j] = getCount(grid[i][j], 5);
        if (i > 0) {
          topPrefix2[i][j] += topPrefix2[i - 1][j];
          topPrefix5[i][j] += topPrefix5[i - 1][j];
        }
      }

    int ans = 0;
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        final int curr2 = getCount(grid[i][j], 2);
        final int curr5 = getCount(grid[i][j], 5);
        final int l2 = leftPrefix2[i][j];
        final int l5 = leftPrefix5[i][j];
        final int r2 = leftPrefix2[i][n - 1] - (j > 0 ? leftPrefix2[i][j - 1] : 0);
        final int r5 = leftPrefix5[i][n - 1] - (j > 0 ? leftPrefix5[i][j - 1] : 0);
        final int t2 = topPrefix2[i][j];
        final int t5 = topPrefix5[i][j];
        final int d2 = topPrefix2[m - 1][j] - (i > 0 ? topPrefix2[i - 1][j] : 0);
        final int d5 = topPrefix5[m - 1][j] - (i > 0 ? topPrefix5[i - 1][j] : 0);
        ans = Math.max(ans, Math.max(Math.max(Math.min(l2 + t2 - curr2, l5 + t5 - curr5),
                                              Math.min(r2 + t2 - curr2, r5 + t5 - curr5)),
                                     Math.max(Math.min(l2 + d2 - curr2, l5 + d5 - curr5),
                                              Math.min(r2 + d2 - curr2, r5 + d5 - curr5))));
      }

    return ans;
  }

  private int getCount(int num, int factor) {
    int count = 0;
    while (num % factor == 0) {
      num /= factor;
      ++count;
    }
    return count;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution:
  def maxTrailingZeros(self, grid: list[list[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    # leftPrefix2[i][j] := the number of 2 in grid[i][0..j]
    # leftPrefix5[i][j] := the number of 5 in grid[i][0..j]
    # topPrefix2[i][j] := the number of 2 in grid[0..i][j]
    # topPrefix5[i][j] := the number of 5 in grid[0..i][j]
    leftPrefix2 = [[0] * n for _ in range(m)]
    leftPrefix5 = [[0] * n for _ in range(m)]
    topPrefix2 = [[0] * n for _ in range(m)]
    topPrefix5 = [[0] * n for _ in range(m)]

    def getCount(num: int, factor: int) -> int:
      count = 0
      while num % factor == 0:
        num //= factor
        count += 1
      return count

    for i in range(m):
      for j in range(n):
        leftPrefix2[i][j] = getCount(grid[i][j], 2)
        leftPrefix5[i][j] = getCount(grid[i][j], 5)
        if j:
          leftPrefix2[i][j] += leftPrefix2[i][j - 1]
          leftPrefix5[i][j] += leftPrefix5[i][j - 1]

    for j in range(n):
      for i in range(m):
        topPrefix2[i][j] = getCount(grid[i][j], 2)
        topPrefix5[i][j] = getCount(grid[i][j], 5)
        if i:
          topPrefix2[i][j] += topPrefix2[i - 1][j]
          topPrefix5[i][j] += topPrefix5[i - 1][j]

    ans = 0
    for i in range(m):
      for j in range(n):
        curr2 = getCount(grid[i][j], 2)
        curr5 = getCount(grid[i][j], 5)
        l2 = leftPrefix2[i][j]
        l5 = leftPrefix5[i][j]
        r2 = leftPrefix2[i][n - 1] - (0 if j == 0 else leftPrefix2[i][j - 1])
        r5 = leftPrefix5[i][n - 1] - (0 if j == 0 else leftPrefix5[i][j - 1])
        t2 = topPrefix2[i][j]
        t5 = topPrefix5[i][j]
        d2 = topPrefix2[m - 1][j] - (0 if i == 0 else topPrefix2[i - 1][j])
        d5 = topPrefix5[m - 1][j] - (0 if i == 0 else topPrefix5[i - 1][j])
        ans = max(ans,
                  min(l2 + t2 - curr2, l5 + t5 - curr5),
                  min(r2 + t2 - curr2, r5 + t5 - curr5),
                  min(l2 + d2 - curr2, l5 + d5 - curr5),
                  min(r2 + d2 - curr2, r5 + d5 - curr5))

    return ans