Rafal's Blog - Codility Passing Cars

Rafal's Blog - Codility Passing Cars
Given an array A of N integers from the set [0,1], interpret 0 as a car travelling east, and 1 as a car travelling west. A car with index P is said to pass car with index Q when P<Q and P is travelling east and Q is travelling west. Count the number of total pairs of cars passing each other.

The naive O(n2) is to go through every element that's travelling east (a 0), and then go through all the elements after it, checking how many are going west (a 1).

This can be improved to O(N) as follows: If we encounter a car going west (a 1), we know that it passes with every car before it that was going east (a 0). By keeping track of how many cars going east we've seen so far, we can easily compute the total number of passing cars.

public int passing_cars(int[] A) {
   int zCount = 0;  // how many going east 
   int passing = 0; // total passing pairs
   
   for(int i : A){
       if(i == 1){
           passing += zCount;
       }
       else zCount++;
   }
   if(passing > 1e9 || passing < 0) return -1;
   else return passing;
}

http://www.martinkysel.com/codility-passingcars-solution/

Count all cars heading in one direction (west). Each car heading the other direction (east) passes all cars that went west so far. Note that east cars at the beginning of the list pass no cars! Also do not forget the upper limit!

def solution(A):

    west_cars = 0

    cnt_passings = 0

    for idx in xrange(len(A)-1, -1, -1):

        if A[idx] == 0:

            cnt_passings += west_cars

            if cnt_passings > 1000000000:

                return -1

        else:

            west_cars += 1

    return cnt_passings

http://www.crazyforcode.com/passing-car-east-west-codility/

http://www.geeksforgeeks.org/count-passing-car-pairs/

An efficient solution to traverse array from right, keep track of counts of 1s from right. Whenever we see a 0, we increment the result by count of 1s.

int getPassingCars(int A[], int n)

{

    // Initialize count of 1s from right

    // and result

    int countOne = 0, result = 0;

    while (n >= 1)

    {

        if (A[n-1] == 1)

            countOne++;

        else

            result += countOne;

        n--;

    }

 

    return result;

}

A simple solution is to use two nested loops. The outer loop searches for a 0, the inner loop counts number of 1s after 0. Finally we return total count.

int getPassingCars(int A[], int n)

{

    int result = 0;

    for (int i=0; i<n-1; i++)

    {

       if (A[i] == 0)

       {

           for (int j=i+1; j<n; j++) 

              if (A[j])

                 result++;

       }

    }

    return result;

}

Read full article from Rafal's Blog - Codility Passing Cars