Painless
PassingCars
Count the number of cars passing through the road.
Given a non-empty array A consisting of N integers. The contiguous elements of array A represent the contiguous cars on the road.
Array A contains 0s, 1s, or both.
For example, consider the following array A:
Example
A [0] = 0
A [1] = 1
A [2] = 0
A [3] = 1
A [4] = 1
There are 5 sets of passing vehicles (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
Write a function:
`class solution {public int solution(int [] A); }
It returns the number of pairs of cars passing by, given a non-empty array A of N integers.
If the number of passing car pairs exceeds 1,000,000,000, the function must return -1.
For example:
Example
A [0] = 0
A [1] = 1
A [2] = 0
A [3] = 1
A [4] = 1
As explained above, the function should return 5.
Write an efficient algorithm for the following assumptions:
Program
PassingCarsSolution.java
public int solution(int[] A) {
int goal = 0;
int[] P = new int[A.length + 1];
P[0] = 0;
for (int i = 0; i < A.length; i++) {
P[i + 1] = P[i] + A[i];
}
for (int j = 0; j < A.length - 1; j++) {
if (A[j] == 0) {
goal += P[P.length - 1] - P[j + 1];
if (goal > 1000000000) {
return -1;
}
}
}
return goal;
}
Detected time complexity:
O(N)
jUnit PassingCarsSolutionTest.java
Report trainingJC2BAT-X4S
Recommended Posts