# Codility - Passing Cars

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

Definitions:
$\mathbf{A} = \{x \in \mathbb{N}\ |0\leq x \leq 1\land |A| = N\},\mathbf{A}\, is\, a\, multiset.$
$\{N \in \mathbb{N}\ |\ 1 \leq N \leq 100,000\}$
Pair: A pair can be described by a tuple $(P, Q)$, such that $0\leq\,P < Q < N \land\,P = 0\land\,Q = 1$;

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.

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

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: Passing Cars Python # 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 123456789101112131415161718192021 # 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)