Codility PassingCars

We are given a vector that contains just zeros and ones, each of them symbolizing a car going east/west-ward. We want to return the number of passing cars. I struggled a bit to understand what was the meaning of this, in the end I found out that we are required to tell how many ones follow each zero.

It helped a lot to look at the provided test case, that I ported here for C++11 and GoogleTest:
TEST(PassingCars, Given)
{
    std::vector<int> input { 0, 1, 0, 1, 1 };
    ASSERT_EQ(5, solution(input));
}
We have to zeros, one at position 0, the other at 2.
The first zero is followed by three ones, the second zero is followed by two ones, hence we are expecting a 5 as a result.

This problem is placed in the Codility Prefix Sum section, so you would probably solve it using the STL partial_sum() function, as I also did in a previous post, when Codility did not support C++11 yet, where you could also find a more in-depth discussion.

Here I refactor only a sleeker solution (credits go to Wen-Kai) that still uses the concept of partial sum, slightly changing it (so that I can't use anymore the STL function) to adhere to the problem requirement:
int solution(std::vector<int>& input)
{
    int sum = 0; // 1
    std::for_each(input.begin(), input.end(), [&sum](int& cur){ // 2
        if(cur == 0) // 3
            ++sum;
        else // 4
            cur = sum;
    });

    unsigned couples = std::accumulate(input.begin(), input.end(), 0U); // 5
    return couples > 1000000000 ? -1 : couples;
}
1. Let's count the number of zeros we see.
2. Loop on all the input items. Notice that I want my lambda function to capture the sum value and to get as parameter the current element in the vector both by reference, so that I can change them. Modifying a input parameter passed by reference is not considered good style, since it could be surprising for the caller. However, it is a common approach in Codility world, for efficiency reason.
3. If the current value is a zero, increase the counter.
4. Otherwise cover the current value (that was a 1) with the number of previously seen zeros.
5. Now we just have to sum all the previously generated partial sums to get the expected result. I should put the value in an unsigned int because a plain int could lead to overflow, given the possible input - in the original post I gave more details on this point and I also provided a test case to ensure my code works right also in extreme situation.
6. The codility problem asks to return -1 when the number of couples is over the one billion threshold.

2 comments:

  1. A clear solution :

    int solution(vector &A) {
    long int passingCars = 0;
    int nToEast = 0;

    for(int n: A){
    if (n == 0){
    nToEast++;
    } else {
    passingCars += nToEast;
    }
    }

    if(passingCars > 1000000000){
    return -1;
    }
    return passingCars;
    }

    ReplyDelete