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

Painless

PassingCars

Count the number of cars passing through the road. image.png

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.

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:


solve

image.png

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


Recommended Posts

[100%] PassingCars (src & junit)
[100%] CyclicRotation (src & jUnit)
[100%] PermMissingElem (src & jUnit)
[100%] FrogJmp (src & jUnit)
[100%] OddOccurrencesInArray (src & jUnit)
[100%] MinAvgTwoSlice (src & junit)
[100%] PermCheck (src & junit)
[100%] TapeEquilibrium (src & jUnit)
[100%] MaxProductOfThree (src & jUnit)
[100%] BinaryGap (src & jUnit)
[100%] MissingInteger (src & junit & author's note)
[100%] [GenomicRangeQuery] (src & junit & author's note)
[100%] MaxCounters (src & junit & author's note)
[100%] Distinct (src & junit & author's note)
junit
JUnit 4 notes
JUnit story
JUnit memorandum