Codility - Passing Cars

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

# 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)

Link to GitHub solution here .
Link to Codility problem here .