Tasks Details
hard
Find a path in given matrix, such that the product of all the numbers on the path has the minimal number of trailing zeros.
Task Score
100%
Correctness
100%
Performance
100%
Matrix A, consisting of N rows and N columns of non-negative integers, is given. Rows are numbered from 0 to N−1 (from top to bottom). Columns are numbered from 0 to N−1 (from left to right). We would like to find a path that starts at the upper-left corner (0, 0) and, moving only right and down, finishes at the bottom-right corner (N−1, N−1). Then, all the numbers on this path will be multiplied together.
Find a path such that the product of all the numbers on the path contain the minimal number of trailing zeros. We assume that 0 has 1 trailing zero.
Write a function:
def solution(A)
that, given matrix A, returns the minimal number of trailing zeros.
Examples:
1. Given matrix A below:
the function should return 1. The optimal path is: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (2,3) → (3,3). The product of numbers 2, 10, 1, 4, 2, 1, 1 is 160, which has one trailing zero. There is no path that yields a product with no trailing zeros.
2. Given matrix A below:
the function should return 2. One of the optimal paths is: (0,0) → (1,0) → (1,1) → (1,2) → (2,2) → (3,2) → (3,3). The product of numbers 10, 1, 1, 1, 10, 1, 1 is 100, which has two trailing zeros. There is no path that yields a product with fewer than two trailing zeros.
3. Given matrix A below:
the function should return 1. One of the optimal paths is: (0,0) → (0,1) → (1,1) → (1,2) → (2,2). The product of numbers 10, 10, 0, 10, 10 is 0, which has one trailing zero. There is no path that yields a product with no trailing zeros.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..500];
- each element of matrix A is an integer within the range [0..1,000,000,000].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 1 minutes
Notes
not defined yet
Code: 20:51:20 UTC,
java,
autosave
Code: 20:51:33 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def path_cost(val):
n2 = 0
n5 = 0
while val % 2 == 0 and val > 0:
n2 += 1
val /= 2
while val % 5 == 0 and val > 0:
n5 += 1
val /= 5
return n2, n5
class Path:
n_2 = 0
n_5 = 0
def cost(self):
return min(self.n_2, self.n_5)
def __init__(self, n_2, n_5):
self.n_2 = n_2
self.n_5 = n_5
def __repr__(self):
return '{}, {}: {}'.format(self.n_2, self.n_5, self.cost())
def step(l: Path, r: Path, n2, n5):
if l is None and r is None:
return Path(n2, n5)
if r is None:
return Path(l.n_2 + n2, l.n_5 + n5)
elif l is None:
return Path(r.n_2 + n2, r.n_5 + n5)
else:
return Path(min(l.n_2, r.n_2) + n2, min(r.n_5, l.n_5) + n5)
def solution(A):
N = len(A)
if A[0][0] == 0 or A[N - 1][N - 1] == 0:
return 1
if N == 1:
n2, n5 = path_cost(A[0][0])
return min(n2, n5)
has_0 = False
B = []
for i in range(N):
B.append([])
for j in range(N):
if A[i][j] == 0:
has_0 = True
n2, n5 = path_cost(A[i][j])
B[-1].append(step(B[i - 1][j] if i > 0 else None, B[i][j - 1] if j > 0 else None, n2, n5))
fin = B[-1][-1]
cost = min(fin.cost(), fin.cost())
if has_0 and cost > 0:
return 1
else:
return cost
Code: 20:51:36 UTC,
py,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def path_cost(val):
n2 = 0
n5 = 0
while val % 2 == 0 and val > 0:
n2 += 1
val /= 2
while val % 5 == 0 and val > 0:
n5 += 1
val /= 5
return n2, n5
class Path:
n_2 = 0
n_5 = 0
def cost(self):
return min(self.n_2, self.n_5)
def __init__(self, n_2, n_5):
self.n_2 = n_2
self.n_5 = n_5
def __repr__(self):
return '{}, {}: {}'.format(self.n_2, self.n_5, self.cost())
def step(l: Path, r: Path, n2, n5):
if l is None and r is None:
return Path(n2, n5)
if r is None:
return Path(l.n_2 + n2, l.n_5 + n5)
elif l is None:
return Path(r.n_2 + n2, r.n_5 + n5)
else:
return Path(min(l.n_2, r.n_2) + n2, min(r.n_5, l.n_5) + n5)
def solution(A):
N = len(A)
if A[0][0] == 0 or A[N - 1][N - 1] == 0:
return 1
if N == 1:
n2, n5 = path_cost(A[0][0])
return min(n2, n5)
has_0 = False
B = []
for i in range(N):
B.append([])
for j in range(N):
if A[i][j] == 0:
has_0 = True
n2, n5 = path_cost(A[i][j])
B[-1].append(step(B[i - 1][j] if i > 0 else None, B[i][j - 1] if j > 0 else None, n2, n5))
fin = B[-1][-1]
cost = min(fin.cost(), fin.cost())
if has_0 and cost > 0:
return 1
else:
return cost
Analysis
Code: 20:51:41 UTC,
py,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def path_cost(val):
n2 = 0
n5 = 0
while val % 2 == 0 and val > 0:
n2 += 1
val /= 2
while val % 5 == 0 and val > 0:
n5 += 1
val /= 5
return n2, n5
class Path:
n_2 = 0
n_5 = 0
def cost(self):
return min(self.n_2, self.n_5)
def __init__(self, n_2, n_5):
self.n_2 = n_2
self.n_5 = n_5
def __repr__(self):
return '{}, {}: {}'.format(self.n_2, self.n_5, self.cost())
def step(l: Path, r: Path, n2, n5):
if l is None and r is None:
return Path(n2, n5)
if r is None:
return Path(l.n_2 + n2, l.n_5 + n5)
elif l is None:
return Path(r.n_2 + n2, r.n_5 + n5)
else:
return Path(min(l.n_2, r.n_2) + n2, min(r.n_5, l.n_5) + n5)
def solution(A):
N = len(A)
if A[0][0] == 0 or A[N - 1][N - 1] == 0:
return 1
if N == 1:
n2, n5 = path_cost(A[0][0])
return min(n2, n5)
has_0 = False
B = []
for i in range(N):
B.append([])
for j in range(N):
if A[i][j] == 0:
has_0 = True
n2, n5 = path_cost(A[i][j])
B[-1].append(step(B[i - 1][j] if i > 0 else None, B[i][j - 1] if j > 0 else None, n2, n5))
fin = B[-1][-1]
cost = min(fin.cost(), fin.cost())
if has_0 and cost > 0:
return 1
else:
return cost
Analysis
Code: 20:51:43 UTC,
py,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def path_cost(val):
n2 = 0
n5 = 0
while val % 2 == 0 and val > 0:
n2 += 1
val /= 2
while val % 5 == 0 and val > 0:
n5 += 1
val /= 5
return n2, n5
class Path:
n_2 = 0
n_5 = 0
def cost(self):
return min(self.n_2, self.n_5)
def __init__(self, n_2, n_5):
self.n_2 = n_2
self.n_5 = n_5
def __repr__(self):
return '{}, {}: {}'.format(self.n_2, self.n_5, self.cost())
def step(l: Path, r: Path, n2, n5):
if l is None and r is None:
return Path(n2, n5)
if r is None:
return Path(l.n_2 + n2, l.n_5 + n5)
elif l is None:
return Path(r.n_2 + n2, r.n_5 + n5)
else:
return Path(min(l.n_2, r.n_2) + n2, min(r.n_5, l.n_5) + n5)
def solution(A):
N = len(A)
if A[0][0] == 0 or A[N - 1][N - 1] == 0:
return 1
if N == 1:
n2, n5 = path_cost(A[0][0])
return min(n2, n5)
has_0 = False
B = []
for i in range(N):
B.append([])
for j in range(N):
if A[i][j] == 0:
has_0 = True
n2, n5 = path_cost(A[i][j])
B[-1].append(step(B[i - 1][j] if i > 0 else None, B[i][j - 1] if j > 0 else None, n2, n5))
fin = B[-1][-1]
cost = min(fin.cost(), fin.cost())
if has_0 and cost > 0:
return 1
else:
return cost
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N**2*log(max(max(A))))
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.040 s
OK
5.
0.036 s
OK
6.
0.036 s
OK
7.
0.036 s
OK
8.
0.036 s
OK
9.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.040 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
6.
0.036 s
OK
7.
0.036 s
OK
8.
0.040 s
OK
9.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
expand all
Performance tests
1.
0.036 s
OK
1.
0.040 s
OK
2.
0.048 s
OK
3.
0.080 s
OK
1.
0.064 s
OK
big_zero_result
all elements in A are neither dividable by 2 or 5; length of A is close to 500
all elements in A are neither dividable by 2 or 5; length of A is close to 500
✔
OK
1.
0.072 s
OK
2.
0.188 s
OK
3.
0.388 s
OK
4.
0.664 s
OK
5.
1.080 s
OK
big_all_dividable
all elements in A are dividable by either power of 2 or 5; length of A is close to 500
all elements in A are dividable by either power of 2 or 5; length of A is close to 500
✔
OK
1.
0.092 s
OK
2.
0.256 s
OK
3.
0.660 s
OK
4.
0.952 s
OK
5.
1.488 s
OK
1.
1.264 s
OK
2.
1.224 s
OK
3.
1.212 s
OK
4.
1.240 s
OK
5.
1.240 s
OK
1.
2.144 s
OK
2.
0.248 s
OK
1.
0.080 s
OK
2.
0.080 s
OK
3.
0.076 s
OK
4.
0.212 s
OK
5.
0.212 s
OK
6.
0.208 s
OK
7.
0.468 s
OK
8.
0.456 s
OK
9.
0.444 s
OK
10.
0.804 s
OK
11.
0.796 s
OK
12.
0.772 s
OK
13.
1.264 s
OK
14.
1.228 s
OK
15.
1.204 s
OK
1.
1.184 s
OK