PassingCars
Task
The task is to count pairs of zeros and ones, where the 1 comes after the 0.
Array A contains only 0s and/or 1s:
- 0 represents a car traveling east,
- 1 represents a car traveling west.
The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.
Solution
For each zero, we need to count the number of ones coming after it, and sum all these values.
This can be done by keeping a running tally of the ones found, counting backwards. This is slightly simpler than the algorithm using prefix sums – which involves two loops through the array.
#include <cassert>
#include <vector>
int solution(vector<int> &A) {
int numOnes = 0, res = 0;
// write your code in C++14 (g++ 6.2.0)
for (int i = A.size() – 1; i >= 0; i–) {
int el = A[i];
assert((el == 0) || (el == 1));
numOnes += el;
if (el == 0)
res += numOnes;
if (res>1000000000) return -1;
} // for
return res;
}This function is O(N)
Test Function
This code tests the solution
int main() {
vector<int> v1{0, 1, 0, 1, 1};
assert(solution(v1) == 5);
vector<int> v2{0, 0, 0};
assert(solution(v2) == 0);
vector<int> v3{1, 1, 1};
assert(solution(v3) == 0);
vector<int> v4{1, 0, 1, 0};
assert(solution(v4) == 1);
vector<int> v5{0, 1, 0, 1, 0, 1};
assert(solution(v5) == 6);
return 0;
}Results
| Correctness | 100% |
| Performance | 100% |