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:

Time Complexity O(N)
Space Complexity O(1)

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

/*Comment here*/