PassingCars

Count the number of passing cars on the road
ℹ️ © Codility, 2009-2018

Problem

A non-empty array A consisting of n integers is given. The consecutive elements of array A represent consecutive cars on a road.
Array A contains only 0’s and/or 1’s:
• 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 that, given a non-empty array A of n integers, returns the number of pairs of passing cars.

The function should return -1 if the number of pairs 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) (not counting the storage required for input arguments).

Solution

C#

class Solution {
  public int solution(int[] A) {
    int r = 0;
    int k = 0;
    foreach (int a in A) {
      if (a == 0) {
        k++;
      } else {
        r += k;
        if (r > 1000000000) {
          return -1;
        }
      }
    }
    return r;
  }
}

Java

class Solution {
  public int solution(int[] A) {
    int r = 0;
    int k = 0;
    for (int a : A) {
      if (a == 0) {
        k++;
      } else {
        r += k;
        if (r > 1000000000) {
          return -1;
        }
      }
    }
    return r;
  }
}

JavaScript

function solution(A) {
  let r = 0;
  let k = 0;
  for (let i in A) {
    let a = A[i];
    if (a == 0) {
      k++;
    } else {
      r += k;
      if (r > 1000000000) {
        return -1;
      }
    }
  }
  return r;
}

PHP

function solution($A) {
  $r = 0;
  $k = 0;
  foreach ($A as $a) {
    if ($a == 0) {
      $k++;
    } else {
      $r += $k;
      if ($r > 1000000000) {
        return -1;
      }
    }
  }
  return $r;
}