Codility passing car

Question

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).

Write a function:

class Solution { public int solution(int[] A); } 

that, given a non-empty zero-indexed array A of N integers, returns the number of passing cars.

The function should return −1 if the number 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.

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.

Complexity:

    expected worst-case time complexity is O(N);
    expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

I don't understand why there are five passing cars, instead of 6. Why doesn't (2,1) count as a passing car? Can someone provide some explanation on how to approach this problem?

Answer 1

Most of the answers here just provided algorithms to solve the task but not answering author original question. "Why is there only 5 pairs of car and not 6 ?" That is because cars (2,1) never pass each other.

Here is quick visualization of problem.

Answer 2

Here is my code that got 100% in C#

class Solution
{
    public int solution(int[] A)
    {
        int count = 0;
        int multiply = 0;
        foreach (int car in A)
        {
            if (car == 0)
            {
                multiply = multiply + 1;
            }
            if (multiply > 0)
            {
                if (car == 1)
                {
                    count = count + multiply;
                    if (count > 1000000000)
                    {
                        return -1;
                    }
                }
            }
        }
        return count;
    }
}

Answer 3

Time Complexity - O(n) Space Complexity - O(1) The logic I came up with goes like this.

• Have 2 variables. Count and IncrementVal. Initialize both to zero.
• Traverse through the array. Every time you find a 0, increment the IncrementVal.
• Every time you find a 1, modify count by adding the incrementVal to count.
• After the array traversal is completed, return back the count.

Note:: Example code provided below assumes static array and a predefined array size. You can make it dynamic using vectors.

#include <iostream>
using namespace std;

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

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

Answer 4

You need to count number of cars passings. Cars are positioned on the road as input says and start driving into either one of directions. 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 0 then count how many 1 elements it has on the right

4. If value of element X is 1 then count how many 0 elements it has on left

5. Repeat for next X

6. Sum up and divide by 2 (cos it takes 2 cars to pass each other), that's the answer.

In case with 0 1 0 1 1 we have 3+1+2+2+2 = 10. Divide by 2 = 5 passings.

We don't count pair 2-1 because 2nd car is driving to the East and never passes the 1st car that is driving away from it to the West.

Answer 5

This is simple example in Java. I think it should be passed on 100%

public int solution(int[] A) {
        int countOfZeros = 0, count = 0;

        for (int i = 0; i < A.length; i++){
            if (A[i] == 0) countOfZeros++;                    
            if (A[i] == 1) count += countOfZeros;    
            if (count > 1000000000) return -1;
        }
        return count;
}

Answer 6

100% JavaScript. The logic behind is that each West car (1) creates a pair with all of the preceding East cars (0). Hence, every time we get a 1 we add all the preceding 0s.

function solution(A) {
    var zeroesCount = 0; //keeps track of zeroes
    var pairs = 0; //aka the result

    for (var i=0; i<A.length; i++) {
        A[i]===0 ? zeroesCount++ : pairs += zeroesCount; //count 0s or add to answer when we encounter 1s

        if (pairs > 1000000000 ) { //required by the question
            return -1;   
        }
    }

    return pairs;
}