[GO] [100%] PassingCars (src & junit)

Painless

PassingCars

Count the number of cars passing through the road.

Task description

Given a non-empty array A consisting of N integers. The contiguous elements of array A represent the contiguous cars on the road.

Array A contains 0s, 1s, or both.

• 0 represents a car moving east
• 1 represents a car moving west. The goal is to count the cars passing by. When P is moving east and Q is moving west, we say that two cars (P, Q) with 0 ≤ P <Q <N are passing.

For example, consider the following array A:

Example

  A [0] = 0
  A [1] = 1
  A [2] = 0
  A [3] = 1
  A [4] = 1

There are 5 sets of passing vehicles (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).

Write a function:

`class solution {public int solution(int [] A); }

It returns the number of pairs of cars passing by, given a non-empty array A of N integers.

If the number of passing car pairs exceeds 1,000,000,000, the function must return -1.

For example:

Example

  A [0] = 0
  A [1] = 1
  A [2] = 0
  A [3] = 1
  A [4] = 1

As explained above, the function should return 5.

Write an efficient algorithm for the following assumptions:

• N is an integer in the range [1..100,000].
• Each element of array A is an integer that can have either 0 or 1 values.

solve

Program

PassingCarsSolution.java

PassingCarsSolution.java

    public int solution(int[] A) {
        int goal = 0;
        int[] P = new int[A.length + 1];
        P[0] = 0;
        for (int i = 0; i < A.length; i++) {
            P[i + 1] = P[i] + A[i];
        }

        for (int j = 0; j < A.length - 1; j++) {
            if (A[j] == 0) {
                goal += P[P.length - 1] - P[j + 1];
                if (goal > 1000000000) {
                    return -1;
                }
            }
        }

        return goal;
    }

Detected time complexity:
O(N)

jUnit PassingCarsSolutionTest.java

Report trainingJC2BAT-X4S