PassingCars at Codility-programmers in C Plus Plus Explained - Count the number of passing cars on the road
Foreword: Category of Article - Technology, Computers and Software, Algorithm
By: Chrysanthus Date Published: 29 Jan 2024
Task
Detected time complexity : O(n)
Lesson 5 at app.codility.com/programmers
The solution and its explanation are given below.
Problem
Title of Problem: PassingCars, for "Cars that cross in Opposite Directions"
A non-empty array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.
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.
For example, consider array A such that:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
Write a function:
int solution(vector<int> &A);
that, given a non-empty array A of N integers, returns the number of pairs of passing cars.
The function should return -1 if the number of pairs of passing cars exceeds 1,000,000,000.
For example, given:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
the function should return 5, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- each element of array A is an integer that can have one of the following values: 0, 1.
Note:
Assume that the cars to the east are using one lane, and the cars to the west are using the opposite lane. Then the cars in question are those that pass each other in opposite directions, and not in the same direction. The goal is to find the number of pairs that will finally cross (pass in opposite directions) one another. Assume that cars going in the same direction, never bypass; that is, such cars are all moving at the same speed.
Brute Force Approach
The brute force approach is to scan the array in two for-loops, one nested; and for every zero, a 1 ahead in the array, makes a pair. In the following table, the pairs are counted (added) from left to right and from top to bottom:
| Index | 0 | 1 | 2 | 3 | 4 |
| Given array | 0 | 1 | 0 | 1 | 1 |
| . | |||||
| 1st inner-loop iteration: pairs (with 1st 0) | 0 | 1 | 1 | 2 | 3 |
| 2nd inner-loop iteration: pairs (with no 0) | 3 | 3 | 3 | 3 | |
| 3rd inner-loop iteration: pairs (with 2nd 0) | 3 | 4 | 5 | ||
| 4th inner-loop iteration: pairs (with no 0) | 5 | 5 | |||
| 5th inner-loop iteration: pairs (with no 0) | 5 (answer) |
These are 15 operations, which are more than 5.log2(5), which is approximately 11.6. n is 5. So, this brute force approach gives, more than n.log2(n) time complexity. The code for this brute force-approach is not provided in this document.
Smart Approach in O(n) Time
Observe from above that as the list (array) is scanned from left to right manually (with the eye), a 1 encountered ahead, makes pairs with all the preceding zeros. By adding (summing) all such pairs, in a prefix sums fashion, the total number of pairs for the task, will be obtained.
Strategy
- First, a list of prefix sums of only zeros is obtained (counting numbers of preceding zeros).
- Next, a list of number of pairs (not summation of pairs) with each 1 encountered is obtained, involving the above list of prefix sums of zeros.
- Next, a list of the prefix sums of pairs are obtained. This prefix sums of pairs, give the number of pairs that have crossed, at any index of the given array. These three operations are going on at the same time in the same body of the loop. The table for this strategy is:
| O(n) Solution (from left to right) | ||||||
|---|---|---|---|---|---|---|
| Index | 0 | 1 | 2 | 3 | 4 | |
| Given array | 0 | 1 | 0 | 1 | 1 | |
| . | ||||||
| Prefix sums for zeros only | 0 | 1 | 1 | 2 | 2 | 2 |
| Given array (re- typed) | 0 | 1 | 0 | 1 | 1 | |
| No. of Pairs from above two rows due to 1 encountered | 0 | 0 | 1 | 0 | 2 | 2 |
| Prefix sums of pairs | 0 | 0 | 1 | 1 | 3 | 5 |
The last-but-one row is obtained from the two preceding rows. A one encountered in the given array (re-typed) forms pairs with all the preceding zeros. All the preceding zeros, is the prefix sum (singular) for zeros only, in the upper cell. The number of pairs is typed directly in a cell of the last-but-one row, below a 1 encountered, from the given array (re-typed). A zero encountered in the given array (re-typed), forms zero number of pairs with preceding zeros, since zeros are cars going east at the same speed and will never cross. This same zero encountered in the given array (re-typed), forms zero number of pairs with preceding ones, since preceding ones are cars that zeros are not still to cross. Zero number of pairs is typed directly in the cell below the 0 encountered in the given array (re-typed). Imagine the cars in the given array as a snapshot of the cars in the street.
Observed that the number of pairs (last-but-one row), when 1 is encountered in the given array (re-typed), is the number of preceding zeros, when 1 is encountered in the given array. All the preceding zeros, is the prefix sum (singular) for zeros only, in the left-top cell above the 1 encountered in the given array (re-typed).
So, prefix sums of number of pairs (last row), is the same as prefix sums for number of preceding zeros, when 1 is encountered (not when 0 is encountered).
The solution for this O(n) approach, can be done using one for-loop, as in the following program (read the code and the comments):
#include <iostream>
#include <vector>
using namespace std;
int solution(vector<int> &A) {
int N = A.size();
int zerosOnlyPrefixs = 0; //equivalent new pairs, when 1 is encountered
int pairsPrefixs = 0;
for (int i=0; i<N; i++) {
if (A[i]==0)
zerosOnlyPrefixs++; //same as: zerosOnlyPrefixs = zerosOnlyPrefixs + 1
else if (pairsPrefixs + zerosOnlyPrefixs <= 1000000000){//no. of pairs so far, must not be > 1000000000
pairsPrefixs = pairsPrefixs + zerosOnlyPrefixs; //A[i] == 1, prefix sum of pairs
}
else { //1000000000 has been attained
return -1;
}
}
return pairsPrefixs; //returns prefix sum of pairs at last index of given vector (array)
}
int main()
{
vector<int> v = {0, 1, 0, 1, 1};
int ret = solution(v);
cout << ret << endl;
return 0;
}
The solution() function without the comments is:
int solution(vector<int> &A) {
int N = A.size();
int zerosOnlyPrefixs = 0;
int pairsPrefixs = 0;
for (int i=0; i<N; i++) {
if (A[i]==0)
zerosOnlyPrefixs++;
else if (pairsPrefixs + zerosOnlyPrefixs <= 1000000000){
pairsPrefixs = pairsPrefixs + zerosOnlyPrefixs;
}
else {
return -1;
}
}
return pairsPrefixs;
}
Conclusion
Strategy
- First, a list of prefix sums of only zeros is obtained (counting numbers of preceding zeros).
- Next, a list of number of pairs (not summation of pairs) with each 1 encountered is obtained, involving the above list of prefix sums of zeros.
- Next, a list of the prefix sums of pairs are obtained. This prefix sums of pairs, give the number of pairs that have crossed, at any index of the given array. These three operations are going on at the same time in the same body of the loop.
The efficient algorithm above, has been made from 1 looking backwards to the preceding zeros, for pairs. The algorithm can still be done from zero, looking ahead to the succeeding ones, for pairs. In other words, instead of doing prefix summing, suffix summing can be done.
The reader should register at app.codility.com/programmers, so that he/she should be testing his/her code.