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

Respectable

MinAvgTwoSlice

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

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.

• Slices (1, 2), the average of which is (2 + 2)/2 = 2;
• Slices (3, 4), the average of which is (5 + 1)/2 = 3;
• Slices (1, 4), the average of which is (2 + 2 + 5 + 1)/4 = 2.5.

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:

• N is an integer in the range [2..100,000].
• Each element of array A is an integer in the range [-10,000..10,000].

solve

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