The problem comes from codility, whose coding problems I'm starting to enjoy as their evaluation criteria really looks at runtime. Task descriptionA non-empty zero-indexed array A consisting of N integers is  given. The consecutive elements of array A represent consecutive  cars on a road.Array A contains only 0s and/or 1s:0 represents a car traveling east,  1 represents a car traveling west.  The goal is to count passing cars. We say that a pair of cars (P, Q),  where 0  P < Q < N, is passing when P is traveling to the east and  Q is traveling to the west.For example, consider array A such that:    A[0] = 0    A[1] = 1    A[2] = 0    A[3] = 1    A[4] = 1  We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3),  (2, 4).Write a function:  def solution(a)that, given a non-empty zero-indexed array A of N integers, returns the number of passing cars.The function should return 1 if the number of passing cars exceeds  1,000,000,000.  For example, given:    A[0] = 0    A[1] = 1    A[2] = 0    A[3] = 1    A[4] = 1  the function should return 5, as explained above.  Assume that:  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.  Complexity:  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).  Elements of input arrays can be modified.SolutionI've tried my hand at 2 different solutions, one where I delete elements from the array but that was slower than my first pass like this:def solution(a)  results = 0  a.each_with_index do |el, i|    if el == 0      j = i      while j <= a.size-1        results += 1 if a[j] != 0        j += 1      end    end    return -1 if results > 1000000000  end  resultsendI understand why this is \$O(n^2)\$, but I'm unsure how to make this faster.
Count cars passing in opposite directions
performance;algorithm;ruby
def solution(a)  results = 0  east_count = 0  a.each do |el|    if el == 0      east_count += 1    else      results += east_count    end    return -1 if results > 1000000000  end  resultsendNote that you don't have to compare each car to every other car.  You just have to track how many are traveling east and each time you find someone going west, increment your results by the eastbound count.  I find this easier to understand than tracking the westbound cars backwards.  r | c--+--0 | 00 | 11 | 1 (0,1)1 | 23 | 2 (0,3), (2,3)5 | 2 (0,4), (2,4)In the table, r stands for results and c stands for east_count.  The pairs found at any point are to the right.  This will not find the pairs that pass, but it does count them.  It maintains the required \$P < Q\$ by order of iteration.  I don't know much about Ruby, so I won't try to make syntactic comments.  Apologies if my own syntax is weak.  This iterates through the array once, so it's \$O(n)\$ in time.  It defines a constant number of scalar variables, so it's \$O(1)\$ memory beyond the input array.  