Solution to Codility lesson3-exercise2 Passing Cars problem, link to Codility problem and complete solution at the end of the post.

**Definitions:**

**Pair:** A pair can be described by a tuple

, such that

;

** Problem:**Define a function

*solution*with input

*A*, such that

*solution*returns the numbers of pairs in array

*A*. If the count is greater than 1,000,000,000 return -1.

- Expected worst-case time complexity is
*O(N)*; - Expected worst-case space complexity is
*O(1);*

**Elements of input arrays can be modified.**** **

### Analysis:

The strategy to solve this problem is, for each car going east or number 0, we add 1 to our counter for cars going east.

11 12 13 |
# Count the numbers of cars going if A[k] == 0: count_zero += 1 |

And for each car going west or number 1 we add the number of cars going east until this moment to the result.

14 15 16 |
# For each car coming add the numbers of cars going before else: result += count_zero |

To complete this task, we have to visit every element of *A, *so the total Time Complexity is *O(N)*.

For the space complexity we have *O(1) *since we have no variable depending on the size input.

**Complete Solution:**

12345678910111213141516171819202122
# Name: PassingCars# Link: https://codility.com/demo/take-sample-test/passing_cars/ def solution(A): N = len(A) result = 0 count_zero = 0 for k in xrange(N): # Count the numbers of cars going if A[k] == 0: count_zero += 1 # For each car coming add the numbers of cars going before else: result += count_zero # -1 if result over 1,000,000,000 if result > 1000000000: return -1 return result

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
# Name: PassingCars # Link: https://codility.com/demo/take-sample-test/passing_cars/ def solution(A): N = len(A) result = 0 count_zero = 0 for k in xrange(N): # Count the numbers of cars going if A[k] == 0: count_zero += 1 # For each car coming add the numbers of cars going before else: result += count_zero # -1 if result over 1,000,000,000 if result > 1000000000: return -1 return result |

*Time Complexity O(N)*

*Space Complexity O(1)*