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%
Task description
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:
class Solution { public int solution(int[][] 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 Java 8
Time spent on task 7 minutes
Notes
not defined yet
Code: 12:03:27 UTC,
java,
autosave
Code: 12:03:52 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
minPws[0][0] = (a[0][0] == 0) ? -1 : pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:04:15 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:04:32 UTC,
java,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:04:54 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:05:04 UTC,
java,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:05:15 UTC,
java,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:05:45 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:06:00 UTC,
java,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
int minPwsVal =
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:06:10 UTC,
java,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
int minPwsVal = minPws[a.length-1][a[0].length-1];
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:06:51 UTC,
java,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
int minPwsVal = minPws[a.length-1][a[0].length-1];
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:07:01 UTC,
java,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
int minPwsVal = minPws[a.length-1][a[0].length-1];
if ()
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:07:31 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
int minPwsVal = minPws[a.length-1][a[0].length-1];
if (minPwsVal == 0) {
}
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:07:43 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
int minPwsVal = minPws[a.length-1][a[0].length-1];
if (minPwsVal == 0) {
return 0;
} else {
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:07:53 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
int minPwsVal = minPws[a.length-1][a[0].length-1];
if (minPwsVal == 0) {
return 0;
}
return minPws[a.length-1][a[0].length-1];
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:08:15 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
int minPwsVal = minPws[a.length-1][a[0].length-1];
if (minPwsVal == 0) {
return 0;
}
return hasZero ? 1 : ;
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:08:25 UTC,
java,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
if (minPws25 == 0) {
return 0;
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if(a[i][j] == 0) {
return 1;
}
}
}
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
int minPwsVal = minPws[a.length-1][a[0].length-1];
if (minPwsVal == 0) {
return 0;
}
return hasZero ? 1 : minPwsVal;
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:08:56 UTC,
java,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
return minPws25;
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
int minPwsVal = minPws[a.length-1][a[0].length-1];
if (minPwsVal == 0) {
return 0;
}
return hasZero ? 1 : minPwsVal;
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:09:06 UTC,
java,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
int minPws25 = min(minPws2, minPws5);
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
int minPwsVal = minPws[a.length-1][a[0].length-1];
if (minPwsVal == 0) {
return 0;
}
return hasZero ? 1 : minPwsVal;
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:09:17 UTC,
java,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
return min(minPws2, minPws5);
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
int minPwsVal = minPws[a.length-1][a[0].length-1];
if (minPwsVal == 0) {
return 0;
}
return hasZero ? 1 : minPwsVal;
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Code: 12:09:52 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
return min(minPws2, minPws5);
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
int minPwsVal = minPws[a.length-1][a[0].length-1];
if (minPwsVal == 0) {
return 0;
}
return hasZero ? 1 : minPwsVal;
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Analysis
Code: 12:10:21 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
return min(minPws2, minPws5);
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
int minPwsVal = minPws[a.length-1][a[0].length-1];
if (minPwsVal == 0) {
return 0;
}
return hasZero ? 1 : minPwsVal;
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}
Analysis
Code: 12:10:25 UTC,
java,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
/**
* @author Anton Fil (https://ua.linkedin.com/in/antonyfil)
*/
class Solution {
public int solution(int[][] a) {
if (a[0][0] == 0 || a[a.length-1][a[0].length-1] == 0) {
return 1;
}
int minPws[][] = new int[a.length][a[0].length];
int minPws2 = getMinPws(a, minPws, 2);
int minPws5 = getMinPws(a, minPws, 5);
return min(minPws2, minPws5);
}
private int getMinPws(int[][] a, int[][] minPws, int p) {
boolean hasZero = false;
minPws[0][0] = pws(a[0][0], p);
//Fullfill the first row
for (int j = 1; j < a[0].length; j++) {
if (a[0][j] == 0 || minPws[0][j-1] == -1) {
hasZero = true;
minPws[0][j] = -1;
} else {
minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
}
}
//Fullfill the first column
for (int i = 1; i < a.length; i++) {
if (a[i][0] == 0 || minPws[i-1][0] == -1) {
hasZero = true;
minPws[i][0] = -1;
} else {
minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
}
}
//Fullfill the rest of matrix
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[0].length; j++) {
if (a[i][j] == 0 || minPws[i-1][j] == -1 && minPws[i][j-1] == -1) {
hasZero = true;
minPws[i][j] = -1;
} else {
int pw = pws(a[i][j], p);
if (minPws[i-1][j] == -1) {
minPws[i][j] = minPws[i][j-1] + pw;
} else if (minPws[i][j-1] == -1) {
minPws[i][j] = minPws[i-1][j] + pw;
} else {
minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pw;
}
}
}
}
int minPwsVal = minPws[a.length-1][a[0].length-1];
if (minPwsVal == 0) {
return 0;
}
return hasZero ? 1 : minPwsVal;
}
private int pws(int n, int p) {
int pws = 0;
if (p == 2) {
while ((n & 1) == 0) {
pws++;
n >>= 1;
}
} else {
while (n % p == 0) {
pws++;
n /= p;
}
}
return pws;
}
private int min(int a, int b) {
return (a < b) ? a : b;
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N**2*log(max(max(A))))
expand all
Correctness tests
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
5.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
5.
0.004 s
OK
6.
0.004 s
OK
7.
0.008 s
OK
8.
0.008 s
OK
9.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.008 s
OK
5.
0.004 s
OK
6.
0.004 s
OK
7.
0.008 s
OK
8.
0.008 s
OK
9.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
expand all
Performance tests
1.
0.004 s
OK
1.
0.008 s
OK
2.
0.012 s
OK
3.
0.036 s
OK
1.
0.016 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.044 s
OK
2.
0.164 s
OK
3.
0.360 s
OK
4.
0.640 s
OK
5.
0.996 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.036 s
OK
2.
0.128 s
OK
3.
0.288 s
OK
4.
0.500 s
OK
5.
0.788 s
OK
1.
1.000 s
OK
2.
1.000 s
OK
3.
0.984 s
OK
4.
0.996 s
OK
5.
0.984 s
OK
1.
1.116 s
OK
2.
0.364 s
OK
1.
0.028 s
OK
2.
0.028 s
OK
3.
0.044 s
OK
4.
0.096 s
OK
5.
0.100 s
OK
6.
0.128 s
OK
7.
0.212 s
OK
8.
0.220 s
OK
9.
0.256 s
OK
10.
0.372 s
OK
11.
0.384 s
OK
12.
0.432 s
OK
13.
0.568 s
OK
14.
0.592 s
OK
15.
0.652 s
OK
1.
0.516 s
OK