Java solution to Codility PassingCars problem (Lesson 5 – Prefix Sums) which scored 100%. The problem is to calculate the number of passing cars on the road. The strategy is to keep a running count of eastbound cars and then for each westbound car encountered, the number of car passes will be the running count of eastbound cars, added to the running count of total passes.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class PassingCars {
public int solution(int[] A) {
int zeros = 0;
int carPasses = 0;
for(int i=0; i<A.length; i++) { if(A[i] == 0) { zeros++; } else if(A[i] == 1) { //for every 1 - there will be an extra car pass for ALL the 0's that came before it carPasses += zeros; if(carPasses > 1000000000) {
return -1;
}
}
else throw new RuntimeException("shouldn't reach here");
}
return carPasses;
}
}
TestNG test cases for this problem which all passed:
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
import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;
import com.codility.lesson05.prefixsums.PassingCars;
public class PassingCarsTests {
private PassingCars solution;
@BeforeTest
public void setUp() {
solution = new PassingCars();
}
@DataProvider(name = "test1")
public Object [][] createData1() {
return new Object [][] {
new Object [] { new int [] { 0, 1, 0, 1, 1 }, 5 },
new Object [] { new int [] { 1, 0, 0, 1, 0, 1 }, 5 },
new Object [] { new int [] { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 }, 15 },
new Object [] { new int [] { 1, 1, 0, 1 }, 1 },
new Object [] { new int [] { 0, 1, 1, 1 }, 3 },
new Object [] { new int [] { 0, 1, 1, 1, 0 }, 3 },
new Object [] { new int [] { 0, 1, 1, 1, 0, 1 }, 5 },
new Object [] { new int [] { 0, 1, 1, 1, 0, 1, 1 }, 7 },
new Object [] { new int [] { 0, 1, 1, 1, 0, 1, 1, 1 }, 9 },
new Object [] { new int [] { 0, 1, 1, 1, 0, 1, 1, 1, 0 }, 9 },
new Object [] { new int [] { 0, 1, 1, 1, 0, 1, 1, 1, 0, 0 }, 9 },
new Object [] { new int [] { 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1 }, 13 },
//no passing cars
new Object [] { new int [] { 1 }, 0 },
new Object [] { new int [] { 0 }, 0 },
new Object [] { new int [] { 0, 0 }, 0 },
new Object [] { new int [] { 1, 1 }, 0 },
new Object [] { new int [] { 1, 1, 0 }, 0 },
};
}
@Test(dataProvider = "test1")
public void verifySolution(int [] pA, int pExpected) {
Assert.assertEquals(solution.solution(pA), pExpected);
}
}