Passing Car East or West Codility

A non-empty zero-indexed 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).

The function should return 5, as explained above.

Assume that:

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.

The function should return −1 if the number of passing cars exceeds 1,000,000,000.

Solution:

When car drives, we can easily see that it will drive by cars moving in the opposite direction, but only if they were in front of it. Essentially that can be formulated as:

(1) Imagine array 0..N

(2) Take element X (iterate from 0 to Nth element)

(3) If value of element X is 1 then count how many 0 elements it has on left

(4) Repeat for next X

Implementation:

int getPassingCars(int* A, int N)
{
    unsigned long count = 0;
    int totalOfZeros = 0;
    for(int i = 0; i < N; i++)
    {
        if(A[i]==0)
        {
            totalOfZeros ++;
        }
        else if (A[i]==1)
        {
            count = count + totalOfZeros;
        }
        if(count > 1000000000) return -1;
    }
    return count;
}

int main()
{
   int A[]={0,1,0,1,1};
   int size = 5;
   int numPasses = getPassingCars(A,size);
   cout << "Number of Passing Cars: " << numPasses << endl;
}

Worst-case time complexity is O(N)

2 Thoughts on “Passing Car East or West Codility

  1. Here is my solution:

    public static int passingCars( int[] a) {

    int passingTotal = 0;
    int eastCount = 0;
    for( int i = a.length – 1; i >=0; –i) {
    if( a[i] == 1) {
    eastCount +=1;
    } else {
    passingTotal += eastCount;
    }
    }

    return passingTotal;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation