title: Codility passing car - how to approach this problem
body: <p>A non-empty zero-indexed array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.</p>
  <p>Array A contains only 0s and/or 1s:</p>
  <pre><code>    0 represents a car traveling east,
      1 represents a car traveling west.
  </code></pre>
  <p>The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P &lt; Q &lt; N, is passing when P is traveling to the east and Q is traveling to the west.</p>
  <p>For example, consider array A such that:</p>
  <pre><code>  A[0] = 0
    A[1] = 1
    A[2] = 0
    A[3] = 1
    A[4] = 1
  </code></pre>
  <p>We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).</p>
  <p>Write a function:</p>
  <pre><code>class Solution { public int solution(int[] A); } 
  </code></pre>
  <p>that, given a non-empty zero-indexed array A of N integers, returns the number of passing cars.</p>
  <p>The function should return −1 if the number of passing cars exceeds 1,000,000,000.</p>
  <p>For example, given:</p>
  <pre><code>  A[0] = 0
    A[1] = 1
    A[2] = 0
    A[3] = 1
    A[4] = 1
  </code></pre>
  <p>the function should return 5, as explained above.</p>
  <p>Assume that:</p>
  <pre><code>    N is an integer within the range [1..100,000];
      each element of array A is an integer that can have one of the following values: 0, 1.
  </code></pre>
  <p>Complexity:</p>
  <pre><code>    expected worst-case time complexity is O(N);
      expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
  </code></pre>
  <p>Elements of input arrays can be modified.</p>
  <p>I don't understand why there are five passing cars, instead of 6. Why doesn't (2,1) count as a passing car? Can someone provide some explanation on how to approach this problem?</p>