# Solution to Passing-Cars by codility

20 Jan

Question Name: PassingCars

### 52 Replies to “Solution to Passing-Cars by codility”

1. Henry says:

Hello Sheng, please I am trying to understand the reasoning behind this solution. I am still struggling to understand the prefix sum principle. If you don’t mind shedding light on this and how this was used to solve this problem, I would be grateful.
Thanks

• Sheng says:

As far as I see, this blog is not a good place to discuss the idea of prefix sum principle. You would better to have an introduction book of algorithm to learn that. Or you could take an open course like Algorithms from Princeton University (https://class.coursera.org/algs4partI-004/).
For the logic behind this solution, you could have a paper and pencil, and draw it as the solution did. Imaging that, all west-driving cars are NOT moving. And only all east-driving cars are moving. In most cases, you could get it.
To be honest, you have to have a solid algorithm basis to do training by Codility. Anyway it is not a textbook for algorithms. Otherwise, it could help little.

2. JG says:

Since I like your solutions, I am posting mine here for anyone who might like to see a different solution.

• Sheng says:

Thanks for sharing your solution, especially for the detailed and great comments!

3. MarkAnd says:

Hey Sheng / JG,
My solution is almost identical to this, less the “if pairs > 1 billion” statement.
Why is that statement necessary? I notice when I submitted my solution I had timeouts, but what specifically should have made me predict this before I submitted my code?

• Sheng says:

Because the challenge requires: The function should return âˆ’1 if the number of passing cars exceeds 1,000,000,000.

• MarkAnd says:

Wow, I’m legitimately embarrassed that I missed that.

• Sheng says:

That is fine. And you are welcome!

4. SP says:

Hello Sheng,
My solution gets 100% correct but 20% performance, what can i do to improve this?

• Sheng says:

• Kim says:

You should avoid using double “for” loop because it will lead worst time complexity of O(N^2) hence diminish the performance of the code severely. I recommend you to try think about how to reduce the loop, so that just one loop will do the job.
Besides, I guess that checking A.Length will not work properly because we are not concerned about the length of the array (in fact, A.Length < 100,000) but the number of passing.

• Sheng says:

Thanks for being a active contributor and helper ðŸ˜‰

5. Simon says:

C++ 11, 100%

• Sheng says:

Thanks a lot for your sharing.
At the same, could you please pay some attention in the details like the input argument signature? In the original post, the parameter is:

which is unworkable. I modified it.
Enjoy coding!

• Tejas Patil says:

This solution doesn’t work for input starts with 1 at 0th index
i.e A ={1,0}; output should be 1.

• Sheng says:

For input [1, 0], the output should be 0.

• Nitesh Jaiswal says:

#Hello Tejas, Your question is pretty genuine and It is a coincidence that I have been asking the same question to myself so below is my solution however, Codility gives me 30% here but as per my test cases below, I still feel my solution should be correct because A = [0,1] or A = [1,0] gives you 1 pair so it sould return 1 not 0 i believe. That is how we count the pairs actually:-

6. Kim says:

The task itself was not very dificult, but the task description was a little bit cryptic to me. As a matter of fact, I think I couldn’t solve this task without the hint shown in this post.
So I thought that it will be gratefully helpful that P and Q are more explicitly stated. That;
P is an index of the array A which represent a car started to traveling to the east, and
Q is an index of the array A which represent a car started to traveling to the west,
so a pair of cars (0,1) means that a car A[0] started to the east and a car A[1] started to the west have been passing.
Anyway, I submitted a survey to the Codility, and hope that they will continue to provide great lessons over and over.
ps. Attached is the code I wrote. Is is basically same as others, but it’s in C.
https://codility.com/demo/results/demoPJ2APK-GAN/
UPDATE: The code I attached above is somewhat wrong. I am deeply sorry for your inconvenience. Please use next code instead.
https://codility.com/demo/results/demo8UZ6J8-CGB/

• Sheng says:

Actually, if you find some description is not clear of misleading, you could contact Codility.com with email. They are very responsible and nice!

7. Enrique says:

Java 100% Correctness

• Sheng says:

Thanks for sharing!

• It would help performance to move this code:

after the loop so you only execute it once.

• Sheng says:

No. The if-closure ends with a “return” statement. No matter it’s included within the loop or after, it will be executed at most once.
In addition, we include the if-closure in the loop for an early termination, to improve the performance. Moving it after loop will make the performance worse.

8. Mathieu says:

A slightly more pythonic solution, that does not call range():

• Sheng says:

Probably we should check the n_paires immediately after updating it. We could get some performance improvement.

9. a131a says:

Ruby 100%

10. ppp says:

11. C# 100%

12. Bogdan says:

A solution using prefix sums which has only 80% at performance despite the fact that it is O(N) (as shown in the result page). Anyone knows what the reason might be?
And also why it shows it’s O(N) and not O(2*N) ?

• Sheng says:

• Tim Murphy says:

Bogdan,
I did the same thing in python and got 100% and 100%. The only difference is a check for count > 1000000000 as count is incremented. I ran your code with this change and got 100% 100%!

13. Bogdan says:

I found an interesting solution, 100% correct but only 40% performance. It starts from the maximum pair count (using combinations of N by 2), substracting not valid pairs in a O(N) step. However, the performance is only 40%. Any idea why ?

• Sheng says:

Overflow!
N could be as large as 100,000. Therefore ((N – 1) * N) / 2 is 4999950000, which is larger than Int32.MaxValue in C#.

• Bogdan says:

Yes, that’s why the count is a long var. And I cast it to int only if it is lower then 1,000,000,000 (the int max value is 2,147,483,647 so it should fit).
The correctness test shows some wrong answers, not time exceeds, like
“got -898714938 expected -1”.
How can the code return big negative values? It looks like some overflows during the conversion.

• Bogdan says:

Ah, yes, I found where is it the overflow: in C# if you make arithmetic operations over an int, the result would be also an int.
So

gets an overflow when N=100.000, no matter the function return type is a long.
So, if we’re boxing the int into a long and perform the arithmetic operations over it, the solution is 100% on Performance test too.

• Bogdan says:

like this:

14. To those, who are having difficulty in understanding the logic, I will give a simple illustration on how the following logic comes. For this let us imagine this , whenever 0 comes , a monk is created and whenever 1 comes, a food is created. We can only count or to say our karma is good , when we serve the food to the monk .And the question is asking, how many times we have served the food to the monk. So, if there are two monks and one food, we need to serve the food to two monks and our karma is 2. Please look upon the illustration given in this image (https://drive.google.com/file/d/0B2GSXjlcPi0lckhCdmdZVXNuZkk/view?usp=sharing). So , by simply adding the times we served the food ( which is equivalent to the pair of car i.e 0,1), we will get total passing car. Please look upon the other illustration on how those counting is done ( https://drive.google.com/file/d/0B2GSXjlcPi0lT3otZ1N5ZXhoZlE/view?usp=sharing). I always have difficulty is understanding the problem and implementation, so I always imagine the problem in other way to properly find the solution.

• Sheng says:

Thanks for your support and explanation!

15. Vygis says:

16. Chima Alaebo says:

Javascript Solution 100%

17. MatB says:

18. Rob Carrington says:

By calling range(len(A)-1, -1, -1), doesn’t this count as space complexity of O(N)? I know in Python 2.7 range() creates a list object.
I am new to this algorithm stuff so I am honestly wondering what the answer is.

• Sheng says:

You are absolutely right. The space complexity is O(N). We could simply improve it by using xrange.

19. ahmed says:

my python solution 100%

20. marian pykalski says:

here it is in C 100%

21. Here’s my VB solution which got 100%. However, I hate to burst everyone’s bubble, but the testing was inaccurate, because none of your solutions work correctly outside of their test cases. Try these arrays for example. [0,0,0,1,1,1,1] , [1,1,1,0,0,0,0]. Why do you get 12 for 1 and 0 for the other? Because it doesn’t work for leading 1’s in the array. I’m still trying to solve that even though it passed I’ve shown it has a major fallacy for leading 1’s.

• Sheng says:

First of all, I would say, to err is human. It’s totally possible that codility testing is defective. I found some and reported.

However, back to your comment, I think you might misunderstood the problem. [0,0,0,1,1,1,1] should output 12, and [1,1,1,0,0,0,0] should result in 0. Let me do a translation ðŸ™‚
[0,0,0,1,1,1,1]: -> -> -> <- <- <- <-, the number of pairs of passing cars is 12 [1,1,1,0,0,0,0]: <- <- <- -> -> -> ->, nobody will pass anyone else.

Hope it helps!

22. Sujal says:

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.
In simple words,
if we see car going to west mean that it can pair with
all previously seen east cars. And also we need add previously
passing_cars counter to get total count. (so prefix sum)

so at point we see west going car in array,
passing_cars[index] = passing_cars[index-1] + east_cars

23. Paaksing says:

Posting just another solution here ;). Went the other way wasting some space complexity that was not necessary but yeah, that’s the only thing went through my mind at the time.

24. Jay Bariya says:

Python solution – 100%. O(N)