2
\$\begingroup\$

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;
}
\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ I appreciate the comments. So thanks for that, although codility's compiler throws the following error: "Solution.cs(32,16): error CS0266: Cannot implicitly convert type uint' to int'. An explicit conversion exists (are you missing a cast?)" After that, adding the cast (int), does pass the tests with 100% final score. The other thing I don't get is why would you throw an ArgumentNullException when just returning that 0 pairsOfPassingCars have been found is OK, and the foreach wouldn't even have to iterate through an empty array? so, no improvement in performance, nor result. Thanks again. \$\endgroup\$ – newbie Sep 28 at 14:02
  • \$\begingroup\$ I was editing (I'm new so I forget about pressing Shift+Enter, when trying to nbsp). Not an important error at all! And of course, I like another point of view (otherwise, why posting here?), and tool for handling overflows :-) If there's another way of doing it (according to the uint part), then I totally get it. My question is, is that way better? I mean you say I can avoid Checked... should I? and why? And the ArgumentNullException I think is unneeded in this context, even though if in general it's a good practice I should follow, then I get it too. \$\endgroup\$ – newbie Sep 28 at 14:12
  • 1
    \$\begingroup\$ I'm sticking to this version of the code. Hope it helps you. \$\endgroup\$ – dfhwze Sep 28 at 14:25
  • 1
    \$\begingroup\$ It did. Considering the fact that overflow checking was unnecessary, made me realize code was perfectly fine without it when I moved if ( pairOfPassingCars > 1000000000 ) { return OVERFLOW; } up. It used to be at the bottom, and returned OVERFLOW if that was true, or pairsOfPassingCars otherwise... That's what made me check \$\endgroup\$ – newbie Sep 28 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.