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.

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:

    function solution($A);

that, given a non-empty zero-indexed 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.


        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.





双重循环绝逼不行, 仔细观察给的例子, 结合双重循环的解法,

可以发现其实双重循环重复计算了很多, 而这些计算往往是前面的


再仔细研究下规律, 可以发现对于第一个0和第二个0而言, 当第二个0

继续遍历遇到1的时候、是一对(0,1)的时候, 对第一个0而言同样是一对(0,1).

由此我们只需要在遍历的时候计算0的个数zero_cnt, 当遇到1的时候我们就将pair_car_cnt增加zero_cnt,



function solution($A) {
    // write your code in PHP5.5
    $zero_cnt = 0;
    $pair_car_cnt = 0;
    foreach ($A as $v) {
        if ($v == 0) {
            $zero_cnt += 1;
        } else {
            $pair_car_cnt += $zero_cnt;
        if ($pair_car_cnt > 1000000000) {
            return  -1;
    return $pair_car_cnt;

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    Markdown is turned off in code blocks:
     [This is not a link](

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see