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. All cars going east will bypass all cars going west.

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:

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

The tutorial (lesson) for this task (problem) is Prefix Sums, so that should suggest to the candidate that prefix sums is needed somehow, to have an efficient algorithm for this task.

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, number of only zeros is being obtained (counting numbers of preceding zeros) as the given array is scanned.

- Next, number of pairs with each 1 encountered is obtained, involving the accumulating number of zeros.

- Next, as the number of pairs with each 1 encountered is obtained, the "prefix sum" (accumulating number of pairs) is also obtained. The table for this strategy is:

O(n) Solution (from left to right)

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;  
    }

The "else if" segment is evaluated when 1 is encountered.

At app.codility.com/programmers, the scoring and detected time complexity for this smart approach is:

    Detected time complexity: constant time, O(N)
    Task score : 100% -  Correctness : 100% ; Performance : 100%

Conclusion

As the given 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 sum fashion, the total number of pairs for the task, will be obtained.

Strategy

- First, number of only zeros is being obtained (counting numbers of preceding zeros) as the given array is scanned.

- Next, number of pairs with each 1 encountered is obtained, involving the accumulating number of zeros.

- Next, as the number of pairs with each 1 encountered is obtained, the "prefix sum" (accumulating number of pairs) is also obtained. The table for this strategy is:

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.