Min Average Two Slice Codility

countdiv codility
an array a consisting of n integers is given. the elements of array a together represent a chain
a non empty array a consisting of n integers is given codility
codility sorting
codility test
codility lessons
codility challenges
codility spark

A non-empty zero-indexed array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1). For example, array A such that:

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

contains the following example slices:

  • slice (1, 2), whose average is (2 + 2) / 2 = 2;
  • slice (3, 4), whose average is (5 + 1) / 2 = 3;
  • slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.

The goal is to find the starting position of a slice whose average is minimal.

Write a function:

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

that, given a non-empty zero-indexed array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice. For example, given array A such that:

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

the function should return 1, as explained above.

Assume that:

  • N is an integer within the range [2..100,000];
  • each element of array A is an integer within the range [−10,000..10,000].

Complexity:

  • expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.


This is my best solution, but obviously not optimal in terms of time complexity. Any ideas?

public int solution(int[] A) {
    int result = 0;
    int N = A.length;
    int [] prefix = new int [N+1];
    for (int i = 1; i < prefix.length; i++) {
        prefix[i] = prefix[i-1] + A[i-1];
    }
    double avg = Double.MAX_VALUE;
    for (int i = 1; i < N; i++) {
        for (int j = i+1; j <=N; j++) {
            double temp = (double)(prefix[j]-prefix[i-1]) /(double)(j-i+1);
            if (temp < avg) {
                avg = temp;
                result = i-1;
            }
        }
    }
    return result;
}

https://codility.com/demo/results/demo65RNV5-T36/


I had posted this some days ago:

Check this out:

http://codesays.com/2014/solution-to-min-avg-two-slice-by-codility/

In there, they explain with great detail why their solution works. I haven't implemented it myself yet, but I will definitely try it.

Hope it helps!

but I just saw it was deleted by a moderator. They say the link is dead, but I just tried it and it works fine. I'm posting it once again, hoping it can be validated that the link is good.

And now I can also provide my implementation, based on the codesays link that I provided before: https://codility.com/demo/results/demoERJ4NR-ETT/

class Solution {
    public int solution(int[] A) {
        int minAvgIdx=0;
        double minAvgVal=(A[0]+A[1])/2; //At least two elements in A.
        double currAvg;
        for(int i=0; i<A.length-2; i++){
            /**
             * We check first the two-element slice
             */
            currAvg = ((double)(A[i] + A[i+1]))/2;
            if(currAvg < minAvgVal){
                minAvgVal = currAvg;
                minAvgIdx = i;
            }
            /**
             * We check the three-element slice
             */
            currAvg = ((double)(A[i] + A[i+1] + A[i+2]))/3;
            if(currAvg < minAvgVal){
                minAvgVal = currAvg;
                minAvgIdx = i;
            }
        }
        /**
         * Now we have to check the remaining two elements of the array
         * Inside the for we checked ALL the three-element slices (the last one
         * began at A.length-3) and all but one two-element slice (the missing
         * one begins at A.length-2).
         */
        currAvg = ((double)(A[A.length-2] + A[A.length-1]))/2;
        if(currAvg < minAvgVal){
            minAvgVal = currAvg;
            minAvgIdx = A.length-2;
        }
        return minAvgIdx;
    }
}

Solution to Min-Avg-Two-Slice by codility – Code Says, The key to solve this task is these two patterns: (1) There must be some slices, with length of two or three, having the minimal average value  MinAvgTwoSlice – Codility – Solution. Java solution to Codility MinAvgTwoSlice problem (Lesson 5 – Prefix Sums) which scored 100%. The problem is to find the minimal average of any slice containing at least two elements. The strategy is to find the minimum average by checking only 2 and 3 contiguous elements at a time.


The tricky part is to figure out even before you start coding that there is for sure an average min slice of length 2 or 3. From there it is easier, but I have a few important notes:

  1. You don't need division at all, you can instead multiply, so that you can get the same average over a slice of length 6 and avoid float operations altogether

  2. You don't need division (or in my case multiplication) in the loop, once in the end it is enough.

  3. If you had to actually do it, you should always compare two floating point numbers like so: EPSILON = 0.0000001 (depending on the precision you look for this can be a different number) and if Math.abs(averageTwo - averageThree) < EPSILON it means they are equal. And you don't need double precision, float is enough.

Here is my solution in Java, it got 100% on Codility:

public int solution(int[] A) {
    if (A.length == 2) return 0;

    int minSliceTwo = A[0] + A[1];
    int minTwoIndex = 0;

    int minSliceThree = Integer.MAX_VALUE;
    int minThreeIndex = 0;

    for (int i = 2; i < A.length; i++) {
        int sliceTwo = A[i - 1] + A[i];
        if (sliceTwo < minSliceTwo) {
            minSliceTwo = sliceTwo;
            minTwoIndex = i - 1;
        }

        int sliceThree = sliceTwo + A[i - 2];
        if (sliceThree < minSliceThree) {
            minSliceThree = sliceThree;
            minThreeIndex = i - 2;
        }
    }
    int averageMinTwo = minSliceTwo*3;
    int averageMinThree = minSliceThree*2;

    if (averageMinTwo == averageMinThree) return Math.min(minTwoIndex, minThreeIndex);
    else return averageMinTwo < averageMinThree ? minTwoIndex : minThreeIndex;
}

Solution (100%) to MinAvgTwoSlice problem on Codility (https , IT'S NECESSARY TO FIND OUT FIRST THAT ONLY SLICES OF LENGTH 2 OR 3 https://codesays.com/2014/solution-to-min-avg-two-slice-by-codility. A slice of length 4 (1,4) contains 5 different subslices (1,2), (1,3), (2,3), (2,4), (3,4). If all elements in the 4 element slice are equal, then all subslices are equal. If there is at least one smaller element, the optimal subslice will contain that element and will be of the shortest possible length.


This is a mathematical problem... and to solve it you have to understand the relationship that exists between the averages of the slices.

We know from the problem description that the slices are a minimum length of 2. The trick to this problem is that the min average slice also cannot be longer than 3. So we only have to calculate the avg of the slices of length 2 and 3.

To understand why the min average slice cannot be longer than 3, consider the case where it is longer than 3...

ex. [-10, 3, 4, -20]

avg(0,3) = -23 / 4 = -5.75 // entire array is -5.75 average
avg(0,1) = -7 / 2 = -3.5 // subslice (0,1)
avg(2,3) = -16 / 2 = -8 // subslice (2,3)

Notice that (avg(0,1) + avg(2,3)) / 2 = avg(0,3) Therefore, if avg(0,1) != avg(2,3) then one of them must be smaller than the other.

No matter which way we split up this array, if the slices aren't exactly the same, then one of them must have a lower average than the full slice. Play around with it and you'll see that it's true. There are mathematical proofs out there.

Codility 'MinAvgTwoSlice' Solution, Short Problem Definition: Find the minimal average of any slice containing at least two elements. Link. MinAvgTwoSlice. Complexity: expected  slice (1, 2), whose average is (2 + 2) / 2 = 2; slice (3, 4), whose average is (5 + 1) / 2 = 3; slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5. The goal is to find the starting position of a slice whose average is minimal. Write a function: def solution(A) that, given a non-empty array A consisting of N integers, returns the starting position of the slice with the minimal average.


100% score with C++ based on Kadane's algorithm

int solution(vector<int> &A) {

    // Find prefix sum.
    int N = A.size();
    vector<int> ps(N + 1, 0);

    for (int i = 1; i <= N; i++) {
        ps[i] = A[i - 1] + ps[i - 1];
    }

    int lft_idx, min_lft_idx;
    double avg_here, min_avg, avg_of_two, avg_with_prev;

    // Initialize variables at the first possible slice (A[0:1]).
    lft_idx = min_lft_idx = 0;
    avg_here = min_avg = (A[0] + A[1]) / 2.0;

    // Find min average of every slice that ends at ith element,
    // starting at i = 2.
    for (int i = 2; i < N; i ++) {

        // average of A[lft_idx : i]
        avg_with_prev = ((double) ps[i + 1] - ps[lft_idx]) / 
                        (i - lft_idx + 1);

        // average of A[i - 1 : i]
        avg_of_two = (A[i - 1] + A[i]) / 2.0;

        // Find minimum and update lft_idx of slice
        // (previous lft_idx or i - 1).
        if (avg_of_two < avg_with_prev) {
            avg_here = avg_of_two;
            lft_idx = i - 1;
        }
        else
            avg_here = avg_with_prev;

        // Keep track of minimum so far and its left index.
        if (avg_here < min_avg) {
            min_avg = avg_here;
            min_lft_idx = lft_idx;
        }
    }

    return min_lft_idx;
}

Although this seems to be a somewhat popular question, based on how many people have already posted their code, I wasn't satisfied with the 2/3-element subslices solution (come on! who would think of that in the duration of an interview?), nor with the explanations (or lack of them).

So I went on searching for other approaches. I found about Kadane's algorithm for the maximum subarray problem (MSP) and then thought of a different solution.

The basic question is (similar to that of the MSP): What is the minimal average of a slice that includes the i-th element?

In order to answer it, we'll look for slices that end in the i-th element, only updating their left index. That is, we have to check for the slices A[lft_idx : i].

Assuming we know the lft_idx of the slice A[lft_idx : i - 1] with a minimal average, then we have two possibilities:

  1. The average of A[lft_idx : i] is minimal.
  2. The average of A[i - 1 : i] is minimal (the shortest possible slice has 2 elements).

What happens in case 1 is that we continue growing the slice that starts at lft_idx.

In case 2, however, we find that growing the previous slice actually increases the average. So we start over again and "reset" the start of the slice (lft_idx) to the previous element (i - 1). Now we have a new best slice of size 2 to grow from this point.

Finally, we want the global minimal average, so we need to keep track of the minimum so far and where it started (the question only asks for this, but we could as well save the right index).

Note: I'm using prefix sums here to calculate slice averages because that's where the question appears in Codility, but it could easily be replaced by a variable with the size of the previous slice and another multiplication.

MinAvgTwoSlice - Codility - Solution, The problem is to find the minimal average of any slice containing at least two elements. The strategy is to find the minimum average by checking only 2 and 3  A number of golden (100%) codility solutions written in Python - wouterken/codility-python


100% score. Javascript.

var min_pos = 0;
var min = Number.MAX_VALUE;

function solution(A) {
  for (var a = 0; a < A.length - 2; a++) {
    process((A[a] + A[a + 1]) / 2.0, a);
    process((A[a] + A[a + 1] + A[a + 2]) / 3.0, a);
  }

  process((A[A.length - 2] + A[A.length - 1]) / 2.0, A.length - 2);
  return min_pos;
}

function process(val, a) {
  if (val < min) {
    min_pos = a;
    min = val;
  }
}

MinAvgTwoSlice coding task - Learn to Code, MinAvgTwoSlice · START. Find the minimal average of any slice containing at least two elements. Programming language:. slice (3, 4), whose average is (5 + 1) / 2 = 3; slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5. The goal is to find the starting position of a slice whose average is minimal. Write a function: class Solution { public int solution(int[] A); } that, given a non-empty array A consisting of N integers, returns the starting position of the slice with the minimal average.


Codility Solutions: Minimum Average Two Slice (MinAvgTwoSlice), A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (​notice that the slice contains at least two elements). The average of a  b) then if we loop through MinA and find the minimum of the array, then this will be the minimum average slice for the whole array (and then return the index position) c) to create this MinA, we start from the second last element of the array and MinA[A.length -2] is the average of the last two elements of A


Solution to Min Average Two Slice - Codility? [on hold], A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (​notice that the slice contains at least two elements). The average of  slice (3, 4), whose average is (5 + 1) / 2 = 3; slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5. The goal is to find the starting position of a slice whose average is minimal.


Best solutions for Codility Lessons. Lesson 5 Prefix Sums, Find the minimal average of any slice containing at least two elements. https://​codesays.com/2014/solution-to-min-avg-two-slice-by-codility/. slice (3, 4), whose average is (5 + 1) / 2 = 3; slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5. The goal is to find the starting position of a slice whose average is minimal.