Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Maximum Trailing Zeros in a Cornered Path LeetCode Solution
Problem – Maximum Trailing Zeros in a Cornered Path LeetCode Solution
You are given a 2D integer array grid of size m x n, where each cell contains a positive integer.
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.
The product of a path is defined as the product of all the values in the path.
Return the maximum number of trailing zeros in the product of a cornered path found in grid.
Note:
- Horizontal movement means moving in either the left or right direction.
- Vertical movement means moving in either the up or down direction.
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.
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 2:
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.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 1051 <= grid[i][j] <= 1000
Maximum Trailing Zeros in a Cornered Path LeetCode Solution in C++
array<int, 2> operator+(const array<int, 2> &l, const array<int, 2> &r) { return { l[0] + r[0], l[1] + r[1] }; }
array<int, 2> operator-(const array<int, 2> &l, const array<int, 2> &r) { return { l[0] - r[0], l[1] - r[1] }; }
int pairs(const array<int, 2> &p) { return min(p[0], p[1]); }
class Solution {
public:
int factors(int i, int f) {
return i % f ? 0 : 1 + factors(i / f, f);
}
int maxTrailingZeros(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), res = 0;
vector<vector<array<int, 2>>> h(m, vector<array<int, 2>>(n + 1)), v(m + 1, vector<array<int, 2>>(n));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
array<int, 2> f25 = { factors(grid[i][j], 2), factors(grid[i][j], 5) };
v[i + 1][j] = v[i][j] + f25;
h[i][j + 1] = h[i][j] + f25;
}
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
auto v1 = v[i + 1][j], v2 = v[m][j] - v[i][j];
auto h1 = h[i][j], h2 = h[i][n] - h[i][j + 1];
res = max({res, pairs(v1 + h1), pairs(v1 + h2), pairs(v2 + h1), pairs(v2 + h2)});
}
return res;
}
};
Maximum Trailing Zeros in a Cornered Path LeetCode Solution in Python
class Solution:
def maxTrailingZeros(self, A: List[List[int]]) -> int:
m, n = len(A), len(A[0])
left = [[[0, 0] for _ in range(n)] for _ in range(m)]
top = [[[0, 0] for _ in range(n)] for _ in range(m)]
def helper(num):
a, b = 0, 0
while num % 2 == 0:
num //= 2
a += 1
while num % 5 == 0:
num //= 5
b += 1
return [a, b]
for i in range(m):
for j in range(n):
if j == 0:
left[i][j] = helper(A[i][j])
else:
a, b = helper(A[i][j])
left[i][j][0] = left[i][j - 1][0] + a
left[i][j][1] = left[i][j - 1][1] + b
for j in range(n):
for i in range(m):
if i == 0:
top[i][j] = helper(A[i][j])
else:
a, b, = helper(A[i][j])
top[i][j][0] = top[i - 1][j][0] + a
top[i][j][1] = top[i - 1][j][1] + b
ans = 0
for i in range(m):
for j in range(n):
a, b = top[m - 1][j]
d, e= left[i][n - 1]
x, y = helper(A[i][j])
a1, b1 = top[i][j]
a2, b2= left[i][j]
tmp = [a1 + a2 - x, b1 + b2 - y]
ans = max(ans, min(tmp))
tmp = [d - a2 + a1, e - b2 + b1]
ans = max(ans, min(tmp))
tmp = [a - a1 + a2, b - b1 + b2]
ans = max(ans, min(tmp))
tmp = [a + d - a1 - a2 + x, b + e - b1 - b2 + y]
ans = max(ans, min(tmp))
return ans
Maximum Trailing Zeros in a Cornered Path LeetCode Solution in Java
public int maxTrailingZeros(int[][] grid) {
//trailing 0, 10->1, 100->2
//10 = 2 * 5
//100 = 2*2*5*5
//etc.
//min(countOf2,countOf5);
//Part 1: move only horizontal
//Part 2: move only vertically
//Part 3: one L turn
//Part 4: one 7 turn
//Part 5: one J turn
//Part 6: one |` turn
//Create PrefixSum array to store count of 2 and 5, then we need O(1) time to get count of 2 or 5.
//matrix count of 2, in row i, from j to k (j<=k) matrix2[i+1][k+1] - matrix2[i+1][j]
int m = grid.length;
int n = grid[0].length;
int[][] matrix2row = new int[m+1][n+1];
int[][] matrix5row = new int[m+1][n+1];
//matrix count of 2, in col i, from j to k (j<=k) matrix[k+1][i+1] - matrix[j][i+1]
int[][] matrix2col = new int[m+1][n+1];
int[][] matrix5col = new int[m+1][n+1];
for(int i = 0;i<grid.length;i++){
// System.out.println(Arrays.toString(grid[i]));
for(int j = 0;j<grid[0].length;j++){
int count2 = count2(grid[i][j]);
int count5 = count5(grid[i][j]);
// System.out.println("grid["+i+"]"+"["+j+"]="+"grid[i][j]"+",count2:"+count2);
matrix2row[i+1][j+1] = matrix2row[i+1][j] + count2;
matrix5row[i+1][j+1] = matrix5row[i+1][j] + count5;
}
}
for(int j = 0;j<grid[0].length;j++){
for(int i = 0;i<grid.length;i++){
int count2 = count2(grid[i][j]);
int count5 = count5(grid[i][j]);
matrix2col[i+1][j+1] = matrix2col[i][j+1] + count2;
matrix5col[i+1][j+1] = matrix5col[i][j+1] + count5;
}
}
//Part 1: move only horizontal
//grid[0][0]->grid[0][n-1]
//grid[1][0]->grid[1][n-1]
//...
//grid[m-1][0]->grid[m-1][n-1]
int ans = 0;
for(int i = 0;i<m;i++){
int count2 = matrix2row[i+1][n]-matrix2row[i+1][0];
int count5 = matrix5row[i+1][n]-matrix5row[i+1][0];
ans = Math.max(ans, Math.min(count2,count5));
}
//Part 2: move only vertically
//grid[0][0]->grid[m-1][0]
//grid[0][1]->grid[m-1][1]
//...
//grid[0][n-1]->grid[m-1][n-1]
for(int j = 0;j<n;j++){
int count2 = matrix2col[m][j+1] - matrix2col[0][j+1];
int count5 = matrix5col[m][j+1] - matrix5col[0][j+1];
ans = Math.max(ans, Math.min(count2,count5));
}
//Find center of + then there are 4 directions
for(int i = 0;i<m;i++){
for(int j =0;j<n;j++){
//up (i,j) to (0,j)
int count2Up = matrix2col[i+1][j+1] - matrix2col[0][j+1];
int count5Up = matrix5col[i+1][j+1] - matrix5col[0][j+1];
//down (i,j) to (m-1,j)
int count2Down = matrix2col[m][j+1] - matrix2col[i][j+1];
int count5Down = matrix5col[m][j+1] - matrix5col[i][j+1];
//left (i,0) to (i,j)
int count2Left = matrix2row[i+1][j+1]-matrix2row[i+1][0];
int count5Left = matrix5row[i+1][j+1]-matrix5row[i+1][0];
//right (i,j) to (i,n-1)
int count2Right = matrix2row[i+1][n]-matrix2row[i+1][j];
int count5Right = matrix5row[i+1][n]-matrix5row[i+1][j];
//3.1 L turn
ans = Math.max(ans,Math.min(count2Up+count2Right-count2(grid[i][j]),count5Up+count5Right-count5(grid[i][j])));
//3.2 7 turn
ans = Math.max(ans,Math.min(count2Up+count2Left-count2(grid[i][j]),count5Up+count5Left-count5(grid[i][j])));
//3.3 |` turn
ans = Math.max(ans,Math.min(count2Down+count2Right-count2(grid[i][j]),count5Down+count5Right-count5(grid[i][j])));
//3.4 J turn
ans = Math.max(ans,Math.min(count2Down+count2Left-count2(grid[i][j]),count5Down+count5Left-count5(grid[i][j])));
}
}
return ans;
}
public int count2 (int x){
int count = 0;
while(x % 2 == 0){
count++;
x = x / 2;
}
return count;
}
public int count5 (int x){
int count = 0;
while(x % 5 == 0){
count++;
x = x / 5;
}
return count;
}
```
Maximum Trailing Zeros in a Cornered Path LeetCode Solution Review:
In our experience, we suggest you solve this Maximum Trailing Zeros in a Cornered Path LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Maximum Trailing Zeros in a Cornered Path LeetCode Solution
Conclusion:
I hope this Maximum Trailing Zeros in a Cornered Path LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More Coding Solutions >>
