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

Respectable

MinAvgTwoSlice

Find the minimum average of slices that contain at least two elements. image.png

Task description

Given a non-empty array A consisting of N integers. A pair of integers (P, Q) such as 0 ≤ P <Q <N is called a slice of array A (note that the slice contains at least two elements). The average slice (P, Q) is the sum of A [P] + A [P + 1] + ... + A [Q] divided by the slice length. To be precise, the mean is equal to (A [P] + A [P + 1] + ... + A [Q])/(Q − P + 1).

For example, the following array A:

Example


    A [0] = 4
    A [1] = 2
    A [2] = 2
    A [3] = 5
    A [4] = 1
    A [5] = 5
    A [6] = 8

The following sample slices are included.

The goal is to find the starting position of the slice with the smallest average.

Write a function:

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

It returns the starting position of the slice with the smallest average given a non-empty array A consisting of N integers. If you have multiple slices with the lowest average, you need to return the smallest starting position for such slices.

For example, given the following array A:

Example


    A [0] = 4
    A [1] = 2
    A [2] = 2
    A [3] = 5
    A [4] = 1
    A [5] = 5
    A [6] = 8

As explained above, the function must return 1.

Write an efficient algorithm for the following assumptions:

solve

image.png

Program MinAvgTwoSliceSolution.java

MinAvgTwoSliceSolution.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];
        }

        double minAvg = 10000;
        for(int j = 0; j < A.length - 1; j++) {
            double currentAvg2 = (double)(P[j + 2] - P[j]) / 2;
            if (currentAvg2 < minAvg) {
                minAvg = currentAvg2;
                goal = j;
            }

            if (j == A.length - 2) break;;

            double currentAvg3 = (double)(P[j + 3] - P[j]) / 3;
            if (currentAvg3 < minAvg) {
                minAvg = currentAvg3;
                goal = j;
            }
        }

        return goal;
    }

Detected time complexity:

O(N)

jUnit MinAvgTwoSliceSolutionTest.java

Report trainingP37RME-WBC


Recommended Posts

[100%] MinAvgTwoSlice (src & junit)
[100%] CyclicRotation (src & jUnit)
[100%] PermMissingElem (src & jUnit)
[100%] FrogJmp (src & jUnit)
[100%] FrogRiverOne (src & jUnit)
[100%] OddOccurrencesInArray (src & jUnit)
[100%] PassingCars (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)
[100%] CountDiv (src & junit & author's note)
junit
JUnit story
JUnit memorandum