Codility's count passing cars in opposite directions in C#

Question

I programmed a few things in java and now I'm learning C#. I've been doing exercises from Codility.

The first 3 or 4 were very difficult to me but now I guess I've got the hang of it. This site helped a lot at improving my style and the things I now think I should be looking at before contenting myself with the final code. I comment a lot less than previous posts because I guess the names and the constants are self explanatory.

• Are there still things to improve in my code in easy exercises like this?

Task score: 100%

Detected time complexity: $O(N)\$

Task description

---

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:

class Solution { public int solution(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.

And this is my solution, please note that if 1000000000+ passing cars are counted, then the return value of the function should be -1. I had to check for overflows, because one of the tests returned a huge negative number if overflowing, also if overflow occurs before 1000000000 (I don't know if an int holds that number), then it would stop counting sooner, hence than try/catch block improves performance(?).

public static int GetNumberOfPassingCars( int[] passingCars )
{
    const int OVERFLOW = -1 ;
    const int EAST = 0 ;
    const int WEST = 1 ;
    int carTravelingEast = 0, pairOfPassingCars = 0;
    foreach( var passingCar in passingCars )
    {
        if ( passingCar == EAST )
        {
            ++carTravelingEast;
        }
        else if ( passingCar == WEST )
        { 
            try
            {
                pairOfPassingCars = checked( pairOfPassingCars + carTravelingEast );
                if ( pairOfPassingCars > 1000000000 )
                {
                    return OVERFLOW;
                }
            }
            catch( OverflowException )
            {
                return OVERFLOW;
            }
        }
    }
    return pairOfPassingCars;
}

Answer 1

Overflow averted

Performance of your algorithm is optimal since you iterate the input just once in \$O(n)\$ time complexity. There is a way to avoid the checked overflow guard. Noone forces you to use int to perform the arithmetic in the method body.

int carTravelingEast = 0, pairOfPassingCars = 0;

Using uint with a max value of \$4,294,967,295\$ would never overflow, since:

• carTravelingEast can never be more than int's max value \$2,147,483,647\$ (because of the length of an array is capped)
• the maximum value \$3,147,483,647\$ as the sum of the custom threshold of one billion + int's max value could never exceed uint's max value (and we exit early on reaching one billion)

Code Conventions

• Don't use UPPERCASE variable names for constants; use PascalCase instead.
• Use white space according to Conventions.
  • GetNumberOfPassingCars( int[] passingCars ) -> GetNumberOfPassingCars(int[] passingCars)
  • foreach( var passingCar in passingCars ) -> foreach (var passingCar in passingCars)
• Use plural name for a variable that represents multiple objects: pairOfPassingCars -> pairsOfPassingCars.
• Use a constant to avoid magic numbers; const uint maxLimit = 1000000000;.
• Throw ArgumentNullException when mandatory arguments are null in public methods.

---

Code Refactored

public static int GetNumberOfPassingCars(int[] passingCars)
{
    if (passingCars == null) throw new ArgumentNullException(nameof(passingCars));

    const int Overflow = -1;
    const int East = 0;
    const int West = 1;
    const uint maxLimit = 1000000000;
    uint carsTravelingEast = 0, pairsOfPassingCars = 0;

    foreach (var passingCar in passingCars)
    {
        if (passingCar == East)
        {
            ++carsTravelingEast;
        }
        else if (passingCar == West)
        { 
            pairsOfPassingCars += carsTravelingEast;
            if (pairsOfPassingCars > maxLimit)
            {
                return Overflow;
            }
        }
    }

    return (int)pairsOfPassingCars;
}