Min Average Two Slice Codility

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/

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;
}

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. Then I found about Kadane's algorithm for the maximum subarray problem (MSP) which led me to 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.

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;
    }
}

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;
}

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.

Why is checking slices of length 2 and 3 sufficient?

This is really what this question comes down to, and asked many times in the comments.

(Mathjax is not supported here, so you'll have to parse the math yourself from the code-formatted text.)

Let A_n be the average of n numbers, B_m the average of the following m numbers. It is easy to check that the average of those m + n numbers combined is

(n * A_n + m * B_m) / (n + m)

Let's say that by extending the slice of A_n to include the numbers of B_m we have found a slice of length m + n with even smaller average. In other words, we assume the following inequality holds

(n * A_n + m * B_m) / (n + m) < A_n.

We can solve this inequality for B_m. Multiply both sides with m + n and subtract n * A_n from each side. Then after dividing by m we conclude:

B_m < A_n.

So this means that B_m is the smallest average of the three slices. We can keep repeating this argument.

Since n >= 2 and m >= 2 the smallest slice that can still be written as a sum of two others in this way, must have length >= 4. Or in other words, the subdividing stops once the last (and therefore minimal) B_m has length < 4, so a length of 2 or 3.

   static public int solution(int[] A) {
    // write your code in Java SE 8

    float avg = 0f;
    int min_index = 0;
    int P = 0;
    //formula

    float sums[] = new float[A.length ];

    //suffix sums
    int prefix = 0;
    for (int i = 0; i < A.length; i += 1) {
        prefix += A[i];
        sums[i] += prefix;
    }
    float min_avg = Float.MAX_VALUE;
    for (int i = 1; i < A.length; i++) {
        avg = (sums[i] - sums[P] + A[P]) / (i - P + 1);
        if (avg < min_avg) {
            min_avg = avg;
            min_index = P;
        }

The idea is rather simple but not so straightforward, A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1) thats the formula there, calculate the prefix sums first.

>formula: min_avg = (prefix[i] - prefix[P] + A[P]) / (i - P + 1)'

        if (A[i] < min_avg) {
            P = i;
        }
    }


    return min_index;


}

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;
  }
}

I think there is logic behind checking slice length <= 3. As per the problem statement the minimum length of a slice can be 2.

> Adding more element to the slice (say slice of length 4) will give us 2 pair of sub-slices whose average will always be less than or equal to the average of slice of length 4. Same is applicable of slice of any size beyond 3. Hence, We need to check slice of length 2 and 3 only. We need not to go beyond Slice of length 3.

Let’s take an example. Consider the following array

> -30,-1,-31,-1,-31,-1,-1, 1, 2, 3,4,45

Choose any slice of length more than 3. Calculate the average, lets say Slice (0, 4) the average is -18.8 but it has a sub-slice (2,4) of length 3 and its average is -21.0. BTW this one is also with the minimum average as well in the given array.

Try all other combination (of length beyond 3) and play around it. You will understand.

Solution without using Prefix sums(100% Score)

    public int solution(int[] A)    {
    float tempAverage,finalAverage = Float.MAX_VALUE;
    int startLocation = 0;
    int lengthOfTheSlice = 0;
    for(int i=0; i < A.length -1; ++i)  {
        tempAverage = (float)(A[i] + A[i+1])/2;
        if(tempAverage < finalAverage)    {
            finalAverage = tempAverage;
            startLocation = i;
            lengthOfTheSlice =2;
        }
    }
    for(int i=0; i < A.length -2; ++i)  {
        tempAverage = (float)(A[i] + A[i+1]+ A[i+2])/3;
        if(tempAverage < finalAverage)    {
            finalAverage = tempAverage;
            startLocation = i;
            lengthOfTheSlice =3;
        }
    }
    System.out.print("Length of the slice \t"+lengthOfTheSlice);
    return startLocation;
}

I understand that http://www.rationalplanet.com/php-related/minavgtwoslice-demo-task-at-codility-com.html provides best explanation and solution that I know so far. Since this is under the prefix sum section, the following is the one I tried to get familiar with the prefix sum method.

function solution($A) {
        // write your code in PHP5.3
        
        $N = count($A);
        if ($N > 100000 || $N < 2 ) {
            return -1;
        } elseif ($N === 2) {
            return 0;
        }

        $presum = array();
        $presum[] = 0;

        $mavg = PHP_INT_MAX;

        $index = 0;
        for ($i = 0; $i < $N; $i++) {                
            $presum[$i+1] = $A[$i] + $presum[$i];
        }

        for ($i = 0; $i < $N-2; $i++) {
            for ($j = $i+1; $j < $i + 3; $j++ ) {
                $avg = ($presum[$j+1] - $presum[$i]) / ($j - $i + 1);

                if ($mavg > $avg) {
                    $mavg = $avg;
                    $index = $i;
                }
            }
        }
        $avg = ($presum[$N] - $presum[$N-2]) / 2;
        if ($mavg > $avg) {
            $index = $N - 2;
        }
        
        return $index;
}

 public int solution(int[] A)
        {
//C# solution thats getting 100%. Once you find min avg with always within 2   //or 3 elements of moving index its much simpler sol
            int minIndex = 0;
            double minAvgVal = Double.MaxValue;

            for (int i = 0; i < A.Length-2; i++)
            {
                double twoDigitMin = (A[i] + A[i + 1])/2.0;
                if (minAvgVal > twoDigitMin)
                {
                    minAvgVal = twoDigitMin;
                    minIndex = i;
                }

                double threDigitMin = (A[i] + A[i + 1] + A[i+2]) / 3.0;
                if (minAvgVal > threDigitMin)
                {
                    minAvgVal = threDigitMin;
                    minIndex = i;
                }
            }

            double last2Avg = (A[A.Length - 2] + A[A.Length - 1])/2.0;
            if (minAvgVal > last2Avg)
            {
                minIndex = A.Length - 2;
            }

            return minIndex;
        }

Here's another Java solution 100/100 using the prefix sums:

public int solution(int[] A) {
        int len = A.length, result = len - 1, sum = 0;
        int[] prefixSums = new int[len + 1];

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

        double min = Double.MAX_VALUE, average = 0d;

        for (int P = 0, Q = 1; Q + 1 < prefixSums.length; ++P, ++Q ) {
            sum = prefixSums[Q + 1] - prefixSums[P];
            average = (sum)/(double) 2;

            if (average < min) {
                min = average;
                result = P;
            }

            if ( Q + 2 < prefixSums.length ) {
                sum = prefixSums[Q + 2] - prefixSums[P];
                average = (sum)/(double) 3;

                if (average < min) {
                    min = average;
                    result = P;
                }
            }

        }

        return result;
    }

Here's the codility link: https://codility.com/demo/results/demo4S4VJX-WMJ/

C++ based on Kanade's algorithm with Prefix Sum's: https://app.codility.com/demo/results/training66V2HC-V6S/

int solution(std::vector<int> &A)
{
    int minIndex = 0;
    auto minAvgVal = std::numeric_limits<int>::max();

    int sumOfTwo = 0;
    int twoDigitSum = 0;
    int threeDigitSum = 0;

    size_t size = A.size();
    for (size_t i = 0; i < (size - 2); ++i) {
        sumOfTwo = A[i] + A[i + 1];
        twoDigitSum = 3 * sumOfTwo;
        if (minAvgVal > twoDigitSum) {
            minAvgVal = twoDigitSum;
            minIndex = i;
        }

        threeDigitSum = (sumOfTwo + A[i + 2]) << 1;
        if (minAvgVal > threeDigitSum) {
            minAvgVal = threeDigitSum;
            minIndex = i;
        }
    }

    sumOfTwo = A[size - 2] + A[size - 1];
    twoDigitSum = 3 * sumOfTwo;
    if (minAvgVal > twoDigitSum) {
        minIndex = (size - 2);
    }

    return minIndex;
}

As you can see, sumOfTwo is an example of using a Prefix Sum.

The key is to notice that the problem is similar with finding minimal avgarge of all slices with length 2 and 3 of a given array.

100% Java solution:

    public int solution(int[] A) {
    int N = A.length;
    double minAvg = Integer.MAX_VALUE;
    double sum = 0;
    int result = 0;
    for (int i = 0; i < N - 1; ++i) {
        sum = A[i];
        for (int j = i + 1; j < i + 3 && j < N; ++j) {
            sum += A[j];
            double avg = (sum / (j-i+1));
            if (avg < minAvg) {
                minAvg = avg;
                result = i;
            }
        }
    }
    return result;
}

Here's a Prefix Sum implementation that works (100% in Codility):

import sys

def solution(A):

    n             = len(A)
    pre_sum       = [0] * (n+1)
    min_slice_avg = sys.maxint
    min_slice_idx = 0

    for i in xrange(1,n+1):
        pre_sum[i] = pre_sum[i-1] + A[i-1]

        # calculate at least 2 prefix sums
        if i-2 < 0: continue

        # check prev 3 slices if we have calculated 3 prefix sums
        if i>=3:
            prev_3_slice_avg = (pre_sum[i] - pre_sum[i-3]) / 3.0

            if prev_3_slice_avg < min_slice_avg:
                min_slice_avg = prev_3_slice_avg
                min_slice_idx = i-3

        # check prev 2 slices
        prev_2_slice_avg = (pre_sum[i] - pre_sum[i-2]) / 2.0

        if prev_2_slice_avg <  min_slice_avg:
            min_slice_avg = prev_2_slice_avg
            min_slice_idx = i-2
        
    return min_slice_idx
    

100 % correctness and performance(java)

void sumArray(int[] A, int[] sum) {
	for (int i = 1; i < sum.length; i++) {
		sum[i] = sum[i - 1] + A[i - 1];
	}
}

int getTotalSum(int[] sum, int start, int last) {
	return sum[last + 1] - sum[start];
}

double minav = Double.MAX_VALUE;
int minind = Integer.MAX_VALUE;

public int solution(int[] A) {
	int[] sum = new int[A.length + 1];
	sumArray(A, sum);
	int startpos = 0;
	for (int i = 1; i <= 2; i++) {
		startpos = 0;
		while (startpos + i < A.length) {
			double suma = getTotalSum(sum, startpos, startpos + i);
			double size = (startpos + i) - startpos + 1;
			double av = suma / size;
			if (av <= minav) {
				
				if (av < minav || startpos < minind) {
					minind = startpos;
				}
				minav = av;
		

			}
			startpos += 1;
		}
	}
	return minind;
}

100% Scala solution

  def solution(a: Array[Int]): Int = {
    val n = a.length
    var min = Double.MaxValue
    var minPos = 0
    for (i <- 0 to n - 2) {
        val sum2: Double = a(i) + a(i+1)
        var avg = sum2 / 2
        if (i < n - 2) {
            avg = Math.min(avg, (sum2 + a(i+2)) / 3)
        }
        if (avg < min) {
            min = avg
            minPos = i
        }
    }
    minPos
  }

A more readable Python solution that gets 100% score:

Pre-calculate the prefix sums:

def prefix_sum(A):
    n = len(A)
    P = [0] * (n + 1)
    for k in range(1, n + 1):
        P[k] = P[k - 1] + A[k - 1]
    return P

This takes 2 and 3 element slices like proposed before and stores the current minimum average and the starting index

def solution(A):
    pref = prefix_sum(A)
    min_mean = 10000
    min_idx_from = 0
    for i in range(len(A)):
        for j in range(i+1,min(i+3,len(A))):
            mean = (pref[j+1] - pref[i]) / (j-i+1)
            if mean < min_mean:
                min_mean = mean
                min_idx_from = i
    return min_idx_from

Measure time:

import random
random.seed(123)
n = 1000
A = [random.randint(-10000, 10000) for _ in range(n)]
%timeit solution(A)
# 1.01 ms ± 3.89 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Codility Link:

https://app.codility.com/demo/results/trainingAK963Y-3NR/

int solution(int A[], int N) {
	// write your code in C99 (gcc 6.2.0)
	int i,j,k;
	int min=A[0];
	int index=0;
	float min_ave=10000;// take the maximum value present in an array
	float temp,ave,req;
	
	for(i=0;i<N;i++)
	{
		if(min>A[i])
		min=A[i];
	}
	
	for(i=0;i<N-1;i++)
	{
		ave=(float)(A[i]+A[i+1])/2;
		
		if(min_ave>ave) // for positive integers minimum slice start point is nothing but start point of two elements with minimum average
		{
			min_ave=ave;
			index=i;
		}
		
		if(A[i]<0)// for negative integers we calculate up to the maximum numbers till there is possibility
		{
			k=1;// number of elements up to current average
			temp=A[i];// sum of number of elements up to current average
			for(j=i+1;j<N;j++)
			{
				k++; 
				req=(A[i]*k)-temp;// 'req' required value of element so that average can be less than current minimum average
				temp+=A[j];
				if((temp/k)<min_ave) // average of k elements
				{
					min_ave=temp/k;
					index=i;
				}
				if(req<min) // A[j] cannot be less than minimum so break
				break;
			}
		}
		if(min_ave==min)
		break;
	}
	return index;
}

My take on the python solution, without prefix sums. I only do one pass over the array

def solution(A):
    min_avg = 10**5
    index = -1
    for i in range(len(A)-1):
        # slice of size 2
        elem_avg = (A[i] + A[i+1])/2
        if elem_avg < min_avg:
            min_avg = elem_avg
            index = i
            
        # Escape checking slice of size 3 if only 2 elements are left
        if i == len(A)-2: continue
        
        # slice of size 3
        elem_avg_3 = (A[i] + A[i+1]+ A[i+2])/3
        if elem_avg_3 < min_avg:
            min_avg = elem_avg_3
            index = i
            
    return index

My 100/100 score solution written in php http://www.rationalplanet.com/php-related/minavgtwoslice-demo-task-at-codility-com.html

My Answer with score 100

public class MinAvgTwoSlice {

public static void main(String[] args) {
	
	System.out.println(new MinAvgTwoSlice().solution(new int[] {4, 2, 2, 5, 1, 5, 8} ));	
}

public int solution(int[] A) {

	double minAvg = 100000;
	int index=0;
	
	if(A.length<=2) {
		
		return 0;
	}
	
	for(int i=0;i<A.length-2;i++) {
		
		if((A[i]+A[i+1])/2.0<minAvg) {
			minAvg=(A[i]+A[i+1])/2.0;
			index=i;
		}

		if((A[i]+A[i+1]+A[i+2])/3.0<minAvg)  {
			
			minAvg=(A[i]+A[i+1]+A[i+2])/3.0;
			index=i;
		}
	}
	
	int aMax = A.length-2;
	
	if((A[aMax]+A[aMax+1])/2.0<minAvg) {
	
		minAvg=(A[aMax]+A[aMax+1])/2.0;
		index=aMax;
	}
	
	return index;
}
}

Thanks : Based on the logic provided in codesays.com

This is my solution written in C (scored 100%)

#include <string.h>

int solution(int A[], int N) {
    // write your code in C99
    
    int *p, i;
    float minAvg, tmpAvg;
    int index=0;
    
    p=malloc(sizeof(int)*(N+1));
    memset(p, 0, sizeof(int)*(N+1));
    
    if(N == 2) {
        return 0;
    }
    
    *p=0;
    
    //Building prefixes vector
    for(i=0;i<N;i++) {
        *(p+i+1)=*(p+i)+A[i];
    }
    
    minAvg=*(p+N)/(float)(N);
    
    for(i=0; i<N-1; i++) {
        tmpAvg=(*(p+i+2)-*(p+i))/(float)(2);
        if (tmpAvg < minAvg) {
            minAvg=tmpAvg;
            index=i;
        }
    }
    
    for(i=0; i<N-2; i++) {
        tmpAvg=(*(p+i+3)-*(p+i))/(float)(3);
        if (tmpAvg < minAvg) {
            minAvg=tmpAvg;
            index=i;
        }
    }
    
    free(p);
    return index;
}

Here is a Go implementation:

func Solution(A []int) int {
    if len(A) < 2 {
	    return -1
    }

    result := 0
    minAvg := float64(A[0]+A[1]) / 2
    var curAvg float64
    for index := 0; index < len(A)-2; index++ {
	    curAvg = float64(A[index]+A[index+1]) / 2
	    if curAvg < minAvg {
		    minAvg = curAvg
		    result = index
	    }

	    curAvg = float64(A[index]+A[index+1]+A[index+2]) / 3
	    if curAvg < minAvg {
		    minAvg = curAvg
		    result = index
	    }
    }

    curAvg = float64(A[len(A)-2]+A[len(A)-1]) / 2
    if curAvg < minAvg {
	    minAvg = curAvg
	    result = len(A) - 2
    }

    return result
}

I got 100% in C#. Try this https://codility.com/demo/results/demoV25DUE-9A8 .

    public static int solution(int[] A)
    {
        float min_avg = (A[0] + A[1]) / 2;
        int minpos = 0;

        for (int i = 0; i < A.Length-2; i++)
        {
            float firsttwo = (float)(A[i] + A[i+1])/2;

            if (firsttwo < min_avg)
            {
                min_avg = firsttwo;
                minpos = i;
            }

            float three = (float)(A[i] + A[i+1] + A[i+2])/3;
            if (three < min_avg)
            {
                min_avg = three;
                minpos = i;
            }

            float lasttwo = (float)(A[i + 1] + A[i + 2]) / 2;
            if (lasttwo < min_avg)
            {
                min_avg = lasttwo;
                minpos = i+1;
            }
        }

        return minpos;
    }

private static int solution(int[] a) {
	// TODO Auto-generated method stub

	int sum=0;
	int absSum=0;
	int minAbsSlice=10000;

	for(int i=0;i<a.length;i++){
		sum=a[i];
		for(int j=1;j<a.length;j++){
			if(j>=i){
				absSum=sum+a[j];
				if(absSum<sum){
					sum=absSum;
					absSum=Math.abs(absSum);

				}else{

					absSum=Math.abs(sum);
					sum=absSum;
				}
			}
		}
		sum=0;
		if(minAbsSlice<absSum){
			minAbsSlice=minAbsSlice;
		}else{
			minAbsSlice=absSum;
		}

	}
	return minAbsSlice;
}

Here is my solution in C++ based on proof that minimal slice must exist with length 2 or 3, see proof at https://codesays.com/2014/solution-to-min-avg-two-slice-by-codility/

Got a score of 100% on Codility for correctness and speed. No need to allocate any memory to solve this, so space for algorithm is O(1), not counting the input vector.

int solution(vector<int> &A) {
    int N             = A.size();
    int minSliceStart = 0;
    
    if (N > 2) {
        // Min Slice must be of length 2 or 3.
        // If Min Slice is longer, 
        //    it must be divisible into smaller parts of equal average
        int min_2_slice_start = 0;
        int min_3_slice_start = 0;
        int min_2_slice_sum   = A[0]+A[1];
        int min_3_slice_sum   = A[0]+A[1]+A[2];
        
        for(int i=0; i<(N-1); i++) {
            int cur_2_slice_sum = A[i]+A[i+1];
            
            // check if the current 2-slice sum is smaller
            if (cur_2_slice_sum < min_2_slice_sum) {
                min_2_slice_sum   = cur_2_slice_sum;
                min_2_slice_start = i;
            }
            
            // check if the current 3-slice sum is smaller
            if (i<(N-2)) {
                int cur_3_slice_sum = A[i]+A[i+1]+A[i+2];
                if (cur_3_slice_sum < min_3_slice_sum) {
                    min_3_slice_sum   = cur_3_slice_sum;
                    min_3_slice_start = i;
                }
            }
        }
        
        #ifdef Want_Debug_Statements
            cout << "2-Slice: start=" << min_2_slice_start << ", sum=" << min_2_slice_sum <<endl;
            cout << "3-Slice: start=" << min_3_slice_start << ", sum=" << min_3_slice_sum <<endl;
        #endif

        // If 2-slice or 3-slice are equal, take the first one.
        // Note: rather than computing averages by dividing,
        // multiple each side by the other denominator instead & compare.
        if (min_2_slice_sum*3 == min_3_slice_sum*2) {
            if (min_2_slice_start < min_3_slice_start)
                minSliceStart = min_2_slice_start;
            else
                minSliceStart = min_3_slice_start;
        } else {
            if (min_2_slice_sum*3 < min_3_slice_sum*2)
                minSliceStart = min_2_slice_start;
            else
                minSliceStart = min_3_slice_start;
        }
    }
    
    return minSliceStart;
}

100% in python :

def solution(A):
 if(len(A) < 2):
     return 0;
 MinAvg=float(A[0]+A[1])/float(2);
 Index=0;
 for nn in range(1,len(A)-1):
     Avg=float(A[nn]+A[nn+1])/float(2);
     if(Avg<MinAvg):
         MinAvg=Avg;
         Index=nn;     
 for nn in range(0,len(A)-2):
     Avg=float(A[nn]+A[nn+1]+A[nn+2])/float(3);
     if(Avg<MinAvg):
         MinAvg=Avg;
         Index=nn;                    
 return Index;     
pass 

For the explanation :

Averaging and comparing on 2 successive elements gives almost the maximal score. Because when one adds an element, if the average is smaller, then the next 2 elements will have a smaller average.

Afterwards remains only the exceptions with 3 elements like [-1, 2, 4, -1, 2, -1].

This is my implementation in Java. I got 100%. The algorithm is the same (sums of 2 and 3 consecutive values), except i didn't use addidional memory for the prefix sums. We don't need all the sums at once, hence we can only hold the current sum, and subtract the mostleft element from the sum as we go to the right.

public int solution(int vect[]) {
	
	double minAvg = (vect[0] + vect[1]) / 2.;
	int minIndex = 0;
	
	double tempAvg = minAvg;
	int tempSum = vect[0] + vect[1];
	int tempIndex = 0;
	int tempLength = 2;
	
	double newAvg;
	int newSum, newIndex;
	
	for(int j=2; j<vect.length; ++j) {
		++tempLength;
		tempSum += vect[j];
		tempAvg = (double)tempSum / tempLength;

		
		newSum = tempSum - vect[tempIndex];
		newIndex = tempIndex+1;
		newAvg = newSum/(j-newIndex+1.);
		
		while(newAvg < tempAvg && newIndex < j) {
			tempIndex = newIndex;
			tempSum = newSum;
			tempAvg = newAvg;
			--tempLength;
			
			newSum = tempSum - vect[tempIndex];
			newIndex = tempIndex+1;
			newAvg = newSum/(j-newIndex+1.);
		}
		
		if (tempAvg < minAvg) {
			minIndex = tempIndex;
			minAvg = tempAvg;
		}
		else if(tempAvg > minAvg && j-tempIndex>1) {
			tempIndex = j;
			tempLength = 1;
			tempSum = vect[j];
		}
	}
	return minIndex;
}

C++ Solution, works fine to me

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.size() < 2) return 0;
    int min_index = 0;
    double min = (A[0] + A[1]) / 2;
    
    for(unsigned int i = 2; i < A.size(); i++){
        
        double temp_three = (A[i - 2] + A[ i - 1] + A[i]) / 3.0;
        double temp_two = (A[ i - 1] + A[i]) / 2.0;
        
        if(temp_three < min){
          min = temp_three;  
          min_index = i - 2;
        } 
        if(temp_two < min){
            min = temp_two;
            min_index = i - 1;
        }
    }
    
    return min_index;
}

In functional programming languages FP like Scala or Haskell, prefix Sums are provided through the Scan Higher Order Function.

In our case the addition HOF function _ + _ is equivalent to the lambda function (x, y) => x + y

https://en.wikipedia.org/wiki/Prefix_sum

FP allows a simpler way to express algorithm that I find easier, for me ,to understand.

The solution scored 100% even with recursion and some few explanations.

https://app.codility.com/demo/results/trainingBZJU4M-NXE/

  def solution(a: Array[Int]): Int = {

    val n: Int = a.length

    /**
      * Let's initialize the prefixSums Array
      */
    val prefixSums: Array[Int] = a.scan(0)(_ + _)

    /**
      * Let's look for a Minimum that has:
      * a position and an average
      * (i.e. Product Type Data Structure)
      */
    case class Minimum(position: Int, average: Float)

    /**
      * Based on a Slice: Position [P] and [Q]
      * Q here is represented by its size [P - Q] (2 or 3)
      * CAPTURE only if there is a change in the minimum average
      */
    def average(p: Int, q: Int, min: Minimum): Minimum = {
      val average: Float = (prefixSums(p + q) - prefixSums(p)) / q.toFloat
      if (average < min.average) min.copy(position = p, average = average) else min
    }

    /**
      * Let's start with the first position
      * and a max average value
      */
    val init = Minimum(position = 0, average = Float.MaxValue)

    /**
      * Let's fold through the A Array indices minus one
      * (paying attention to the slice size)
      *
      * while capturing the minimum average.
      * If Q size reaches 3 (instead of regular slice tuple:
      *    capture the last minimum average
      *    otherwise return the current minimum average
      * give the minimal position
      */
    (0 until n - 1).toList
      .foldLeft(init) { (min, p) =>
        val currentMin = average(p, 2, min)
        if (p < n - 2) average(p, 3, currentMin) else currentMin
      }.position

  }

Python solution (100% pass)

def find_2_lowers(A):
    total = 10001 + 10001
    x_pos = 0
    y_pos = 0
    for i,j in zip(range(len(A)), range(1, len(A))):
        if j == len(A):
            return x_pos, y_pos, total
        if A[i] + A[j] == total:
            continue #ignoring the more deeply index
        elif A[i] + A[j] < total:
            total = A[i] + A[j]
            x_pos = i
            y_pos = j
        

    return x_pos, y_pos, total

def find_3_lowers(A):
    total = 10001 + 10001 + 10001
    x_pos = 0
    y_pos = 0
    z_pos = 0
    for i,j,k in zip(range(len(A)), range(1, len(A)),range(2, len(A))):
        if k == len(A):
            return x_pos, y_pos, z_pos, total
        if A[i] + A[j] + A[k] == total:
            continue #ignoring the more deeply index
        elif A[i] + A[j] + A[k] < total:
            total = A[i] + A[j] + A[k]
            x_pos = i
            y_pos = j
            z_pos = k

    return x_pos, y_pos, z_pos, total

def solution(A):
    if len(A) <= 2:
        return 0
    
    x2,y2,total2 = find_2_lowers(A)
    x3,y3,z3,total3 = find_3_lowers(A)
    
    #print("x2,y2,total2 ", x2,y2,total2 )
    #print("x3,y3,z3,total3 ", x3,y3,z3,total3 )
    
    if total2/2 < total3/3:
        return x2
    elif total2/2 == total3/3:
        return min(x2, x3)
    return x3

Solution in python with little explanation, hope it helps some one. Codility Python 100%

import sys


def solution(A):
"""
https://app.codility.com/demo/results/training3K95ND-KGH/
100%
Idea-
Idea is to calculate the prefix some and find out the average as per given formula in this problem and determine minimum slice starting index
Prefix sum - is used to avoid the two loops to calculate the sum of array Items
Find min average from P to Q in array and store the minimum index and say it as average of slice from p to q
Objective is to find minimum average of other slice, the next slice can be [next q+1 and either include  p,q,q+1 p or exclude q,q+1]
We can exclude the slice calculated so far if the current item is less than the average

   """

min_index = 0
print(A)
# why prefix some? - just to calculate the some between two places without using two loops
prefix_sum = [0] * len(A)
prefix_sum[0] = A[0]
for i in range(1, len(A)):
    prefix_sum[i] = prefix_sum[i - 1] + A[i]
print(prefix_sum)

min_avg = sys.float_info.max
# start from slice p ie. from start, this is start and act as P in problem statement and Q would be the q_end_index as shown below
slice_p_from_index = 0
for q_end_index in range(1, len(A)):
    # for q_end_index = 1 - at this time calculating average from 0 to 1
    # as per problem statement (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1)
    print("From P:slice_p_from_index= " + str(slice_p_from_index) + "  To Q: i= " + str(q_end_index) + " slice " + str(A[slice_p_from_index:q_end_index + 1]))
    print("Slice length " + str(q_end_index - slice_p_from_index + 1))
    # get the some for position P,Q - ie. from slice_p_from_index to i positions and davide by the slice length
    average = (prefix_sum[q_end_index] - prefix_sum[slice_p_from_index] + A[slice_p_from_index]) / (q_end_index - slice_p_from_index + 1)
    # check for minimum average so far
    if average < min_avg:
        min_avg = average
        # hold the index for minimum average value
        min_index = slice_p_from_index

    print("min_avg " + str(min_avg))
    # this is to find out the next starting position for slice_p_from_index
    # idea is to skip all the items found so far up to q_end_index-1, to skip and start from q_end_index we have to proof that the next slice min average
    # can be less than the current minimum average
    # that can only happen if and only if current Item A[q_end_index] is less than the minimum average
    # if so we start taking array slice from current Item A[q_end_index] and make slice with next Item
    print("Index = " + str(q_end_index) + " Item " + str(A[q_end_index]))
    if A[q_end_index] < min_avg:
        print("min index found....Item < min_avg, slice_p_from_index changed to Index")
        slice_p_from_index = q_end_index
    print("")
return min_index

Run-

"""
Run - 
[4, 2, 2, 5, 1, 5, 8]
[4, 6, 8, 13, 14, 19, 27]
From P:slice_p_from_index= 0  To Q: i= 1 slice [4, 2]
Slice length 2
min_avg 3.0
Index = 1 Item 2
min index found....Item < min_avg, slice_p_from_index changed to Index

From P:slice_p_from_index= 1  To Q: i= 2 slice [2, 2]
Slice length 2
min_avg 2.0
Index = 2 Item 2

From P:slice_p_from_index= 1  To Q: i= 3 slice [2, 2, 5]
Slice length 3
min_avg 2.0
Index = 3 Item 5

From P:slice_p_from_index= 1  To Q: i= 4 slice [2, 2, 5, 1]
Slice length 4
min_avg 2.0
Index = 4 Item 1
min index found....Item < min_avg, slice_p_from_index changed to Index

From P:slice_p_from_index= 4  To Q: i= 5 slice [1, 5]
Slice length 2
min_avg 2.0
Index = 5 Item 5

From P:slice_p_from_index= 4  To Q: i= 6 slice [1, 5, 8]
Slice length 3
min_avg 2.0
Index = 6 Item 8

Solution 1

"""

I hope it helps at least one user.

I do now want to just copy-paste my solution in java. But want to speak , little bit about problem, and my view. First of all, this is my heaviest task on Codility. Already solved difficult ones with 100% perfect score, but this was different. The task explanation from Codility if tricky one and can lead (my case) to the wrong solution. First i know that slice must be at least 2, but how long exactly. I used prefix sums before and solved problems in sections before with this. But here i did now where to start.. and then got hint from youtube friend, in her video (she is python addict but logic is what I needed in lack of mine), she did not give the solution, she only give partial solution of n%, and a hint to find one.. you "need to check slices 2 and 3" (i think that I can watch task for ages, and do not try this).

her video https://www.youtube.com/watch?v=w0eFQwiKY7k&lc=z22kcx1jbm3dgxmmtacdp43aah2bhysshyiae2xmrzdw03c010c.1582810577807791

the best prefix sums video ever to exist (very helpful!) https://www.youtube.com/watch?v=scD312I7kkE

class Solution {
    public int solution(int[] A) {
        int ind = 0;
        if (A.length > 3) {
            //make min value double increase corectness to  80%
            double min = (double) (A[0] + A[1]) / 2;
            ind = 0;
            for (int n = 1; n < A.length; n++) {
                A[n] = A[n] + A[n - 1];
            }
            for (int m = 1; m < A.length - 1; m++) {
                if (m + 2 < A.length) {
                    if ((double) (A[m + 2] - A[m - 1]) / 3 < min) {
                        min = (double) (A[m + 2] - A[m - 1]) / 3;
                        ind = m;
                    }
                }
                if ((double) (A[m + 1] - A[m - 1]) / 2 < min) {
                    min = (double) (A[m + 1] - A[m - 1]) / 2;
                    ind = m;

                }
            }
            //added
            if ((double) (A[2]) / 3 < min) {
                min = (double) (A[2]) / 3;
                ind = 0;
            }
            if ((double) (A[1]) / 2 < min) {
                min = (double) (A[1]) / 2;
                ind = 0;
            }
            return ind;
        }
        return ind;
    }
}

Hope this helps, Happy coding, Nenad

This is my Approach in C++( slice with 2 elements only should we do for more elements?)

int solution(std::vector<int> &A)
{
std::vector<double>slice_sum;
for (int i = 0; i < A.size()-2; ++i)
{
	slice_sum.push_back((A[i] + A[i + 1])/2);	
}
int index= std::min_element(slice_sum.begin(), slice_sum.end())- slice_sum.begin();
if (A[index]>=A[index +1])
	{
		return index;
	}
else
	{
		return (index + 1);
	}
}

Finally could get score 100/100 using Streams !!!!!!

> I LOVE LAMBDAS

return IntStream.range(0, A.length - 2)
            .reduce((i1, i2) -> {
                double iFirst = Math.min((double) (A[i1] + A[i1 + 1]) / 2, (double) (A[i1] + A[i1 + 1] + A[i1 + 2]) / 3);
                double iSecond = Math.min((double) (A[i2] + A[i2 + 1]) / 2, (double) (A[i2] + A[i2 + 1] + A[i2 + 2]) / 3);
                if (A.length - 3 == i2) {
                    double last = (double) (A[i2 + 1] + A[i2 + 2]) / 2;
                    return iFirst <= iSecond && iFirst <= last ? i1 : iSecond <= last ? i2 : i2 + 1;
                }
                return iFirst <= iSecond ? i1 : i2;
            }).orElse(0);

Score 100% Simple solution

def solution(A):
    # write your code in Python 3.6
    #initialize  as 0<= P<Q<N(len(A)) is given
    Q=len(A)-1
    avg=(A[0]+A[1])/2
    Mini_Position=0
    
    #Two Slice
  
    for P in range(Q):
        average_two=sum(A[P:P+2])/2.0
        
        if avg > average_two:
            avg=average_two
            Mini_Position=P
    #three slice
    for P in range(Q-1):
        average_three=sum(A[P:P+3])/3.0
      
        if avg >average_three:
            avg =average_three
            Mini_Position=P
        
   
   
    return Mini_Position

My 100% solution in Go. https://app.codility.com/demo/results/trainingV5TF7T-XK6/

func MinAvgTwoSliceSolution(A []int) int {
	// min slice len will always be less than 4 , 
	// imagine a slice of len 4 which can be divided in two slices of 
	// len 2 which either has same avg or 
	// any one of them having lesser avg (the other one will be greater)

	var start int
	min := float64(A[1]+A[0]) / 2

	for i := 2; i < len(A); i++ {
		avg := float64(A[i-1]+A[i]) / 2
		if avg < min {
			min = avg
			start = i - 1
		}

		avg = float64(A[i-2]+A[i-1]+A[i]) / 3
		if avg < min {
			min = avg
			start = i - 2
		}
	}

	return start

}

I think the logic (expressed in words) of why only 2 and 3 sub arrays need checking is not so much that 'we can't have a MAV (minimal average value) longer than 3' but that if it is longer than 3, the starting position of that MAV subarray won't change. I.e. it won't move forward. Suppose we'd have said that we could have subarrays of MAV (although 'average' doesn't then make sense anymore) of even length 1, we'd have only needed to check subarrays of size 1 and 2.

So why is is that once you find for a given starting point that sub of size 3 is smaller than sub of size 2, you don't need to check any further and can safely say that the starting point of sub size 3 is the smallest starting point for any further calculated averages? (Btw, when I say a given 'starting point' I mean this: eg -> { 4, 3, 2, 1, 2, 1, 4 }. If we choose starting point index 3, then we might first view from index 3 to index 6 as an array M of itself and then to find the first index of the MAV subarray S within M, we only need to check combinations: {1 2} and {1 2 1}.)

So, I think the logic to that is, first, you know that dividing the entire array M by two, no matter where the split is, will always give you either two sub arrays whose own averages are equal or one is less than the other but combined will equal the average of their parent = M. Now if you see that sub of size 3 is less than size 2 you know that should further subarrays [i.e. of bigger sizes within M] get smaller, that same fact tells you that the rate of content increase [i.e. the integers/content you're getting by each added subsequent index] is smaller compared to the divisor increase [i.e. the index numbers that are constantly increasing by 1] and so, as long this is true, the starting index cannot move.

On the other hand, if bigger subarrays will begin to increase, you needn't worry that at the end they'll be bigger than the subarray size 2 [within M] that you've previously checked because even if it does become bigger, they will still always contain a subarray of MAV smaller than the one of size 2 you've checked earlier and you can always choose not to include them [i.e. stop before them] and remain proclaiming the starting index of the subarray of just size 3, as the starting index of the MAV subarry of M. Then after checking all 2s and 3s, choosing each element of the original array as a 'starting point' you take the smallest of them all as the MAV for the entire original array. (Note, had you seen that subarray of size 3 is equal to sub of size 2, you'd have not changed the starting index from pointing at the beginning of subarray of size 2 to pointing to the beginning of sub of size 3 and indeed, sub of size 2 would have then contained the MAV or rather the 'first' MAV in M (as per the provisions in the instructions on codility).

My solution in C#. It's a little hard to read because It was a refactoring of a previous solution which had n*n-1/2 run time or something like that and is done with just one While loop but it uses prefix sums.

 public static int solution(int[] A)
        {

            int[] B = new int[A.Length + 1];
            int i = 0;
            int j = 1;
            int copiedVal = A[1];
            A[1] = A[1] + A[0];
            double min = (double)A[1] / 2;
            int pos = 0;
            while (j < A.Length - 1 || (j < A.Length && i == 0))
            {
                B[i + 1] = B[i] + A[i + j];

                if ((double)B[i + 1] / (i + 2) < min)
                {
                    min = (double)B[i + 1] / (i + 2);
                    pos = j - 1;
                }

                if (i == 1)
                {
                    A[j] = copiedVal;
                    j++;
                    copiedVal = A[j];
                    A[j] = A[j] + A[(j - 1)];
                    i = -1;

                }
                i++;

            }

            return pos;
        }

I don't have proof that the slice with minimum average is only either 2 elements or 3 elements, so I made an answer without that proof. The idea is that the next element can only reduce the current average if its value is below the current average.

Got 100% in Codility. Link

// you can use includes, for example:
// #include <algorithm>
#include <limits>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int result = 0;
    float min_average = std::numeric_limits<float>::max();

    for (vector<int>::iterator it = A.begin(); it < (A.end() - 1); it++) {
        int current_total = *it + *(it + 1);
        unsigned int counter = 2;
        float current_average = float(current_total) / counter;

        while (((it + counter) < A.end())
        && (*(it + counter) < current_average)) {
            current_total += *(it + counter);
            current_average = float(current_total) / (counter + 1);
            counter++;
        }

        if (current_average < min_average) {
            min_average = current_average;
            result = it - A.begin();
        }
    }

    return result;
}

public int solution(int[] A) {
    // write your code in Java SE 8

	int index = 0;
	
	int len = A.length;
	if(len == 2) {
		return 0;
	}
	double min = Double.MAX_VALUE;
	if( len == 3) {
		index = ((double)(A[0] +A[1])/2) < ((double)(A[1] +A[2])/2) ? 0:1;
		return index;
	}
	
	double minM =Double.MAX_VALUE;
	for(int i = 0; i< len  -3; i++) {
		minM = (((double)(A[i] + A[i+1])/2) < ((double)(A[i] +A[i+1]+A[i+2])/3)? ((double)(A[i] +A[i+1])/2) : ((double)(A[i] +A[i+1]+A[i+2])/3));
		index = min <= minM ? index : i; 
		min = min <= minM ? min :minM; 
		
	}
	if (((double)(A[len-3]+A[len-2] +A[len-1])/3) <= ((double)(A[len-2] +A[len-1])/2) )
		index = ((double)(A[len-3]+A[len-2] +A[len-1])/3) < min ? len-3 : index;
	else
		index =  ((double)(A[len-2] +A[len-1])/2) <  min? len-2: index;
	
	return index;
}

https://app.codility.com/demo/results/trainingGJHXWR-8KU/

Shortest you can do to get 3 * 100% in Java:

double minavg = Double.MAX_VALUE;
        int minSliceIndex = 0;

        for(int p = 0; p < A.length - 1; p++) {
            int sum2 = A[p] + A[p + 1];
            double avg2 = sum2 / 2.0d;
            if(avg2 < minavg) {
                minavg = avg2;
                minSliceIndex = p;
            }

            if(p < A.length - 2) {
                double avg3 = (sum2 + A[p + 2]) / 3.0d;
                if(avg3 < minavg) {
                    minavg = avg3;
                    minSliceIndex = p;
                }
            }
        }
        
        return minSliceIndex;

My python answer that got 100% on codibility:

def solution(A):
amin = sum(A)/len(A)
imin = 0

for i in range(0, len(A)-1):
    sij = A[i]

    for j in range(i+1, i+3):
        if j < len(A):
            sij += A[j]
            aij = sij/(j-i+1)

            if aij < amin:
                amin = aij
                imin = i

return imin

My 100% Solution in Javascript that is easy to understand:

function solution(A) {
  let lowestSum = Number.MAX_SAFE_INTEGER;
  let result;

  // Check if slices of 2 are the solution
  for (let i = 0; i < A.length - 1; i++) {
    if ((A[i] + A[i + 1]) / 2 < lowestSum) {
        lowestSum = (A[i] + A[i + 1]) / 2;
        result = i;
    }
  }

  // Check if slices of 3 are the solution
  for (let i = 0; i < A.length - 2; i++) {
    if ((A[i] + A[i + 1] + A[i + 2]) / 3 < lowestSum) {
        lowestSum = (A[i] + A[i + 1] + A[i + 2]) / 3;
        result = i;
    }
  }

  return result;

}

Why this works?

According to CodeSays, if there exists a solution slice of more than 3, it can be broken into slices of 2 or slices of 3, that are also a solution. Hence why we are only checking those two.

Here is my simple solution with 100% Score Complexity(On)

function solution(A) {
    let minAvg = Number.MAX_SAFE_INTEGER;
    let minAvgPos = 0;
    if(A.length === 2) return minAvgPos;
    for (let p = 0; p < A.length-1; p++) {
        const sumSlice2 = A[p] + A[p+1];
        const avgSlice2 = sumSlice2 / 2;

        if (avgSlice2 < minAvg) {
            minAvg = avgSlice2;
            minAvgPos = p;
        }

        const sumSlice3 = A[p] + A[p+1] + A[p+2];
        const avgSlice3 = sumSlice3 / 3;
        if (avgSlice3 < minAvg) {
            minAvg = avgSlice3;
            minAvgPos = p;
        }
    }

    return minAvgPos;
}

def solution(A):
    all_avg = 10**10
    p = 0
    first_2_avg = sum(A[:2])/2
    for i in range(3, len(A)+1):
        avg_3 = sum(A[i-3:i])/3
        avg_2 = sum(A[i-2:i])/2
        c = avg_3 if avg_3 < avg_2 else avg_2
        if c < all_avg:
            all_avg = c
            c_p = i-2 if avg_3 < avg_2 else i-1
            p = c_p-1
    return 0 if all_avg >= first_2_avg else p

we can make sure we have the smallest avg with the help of this assumption: let's say we have a slice of [a, b, c, d]. how can we relate avg([a, b, c, d]) to avg([a, b]) and avg([c, d])? we can relate them like min(avg([a, b]), avg([c, d])) <= avg([a, b, c, d])

Python 100%

Previous solutions especially python are a bit complicated so I wrote a simpler solution.

I followed Kadane's Algorithm https://www.youtube.com/watch?v=86CQq3pKSUw which enables us to find the min slice position with only one loop.

Detected time complexity is O(N)

def solution(A):

    starting_avg = (A[0] + A[1]) / 2
    avg_a = avg_b = global_avg = starting_avg

    pos_min_slice = 0

    for i in range(1, len(A)-1):

        avg_a = min(avg_a, (A[i] + A[i+1]) / 2)
        if avg_a < global_avg:
            global_avg = avg_a
            pos_min_slice = i

        avg_b = min(avg_b, (A[i-1] + A[i] + A[i+1]) / 3)
        if avg_b < global_avg:
            global_avg = avg_b
            pos_min_slice = i-1

    return pos_min_slice

My 100% JavaScript solution with O(N) time complexity:

function solution(A) {

    let index = 0; // default slice index
    let minAvgGlobal = 10000; // max integer value inside A

    for (let p = 0, len = A.length; p < len - 1; p++) {
        const first = A[p];
        const second = A[p + 1];
        const third = A[p + 2] !== undefined ? A[p + 2] : Infinity;
        // in case we are accessing undefined element at the end, Infinity / 3 is still Infinity
        const twoSliceAvg = (first + second) / 2;
        const threeSliceAvg = (first + second + third) / 3;
        const minAvg = Math.min(twoSliceAvg, threeSliceAvg);
        if (minAvg < minAvgGlobal) {
            minAvgGlobal = minAvg;
            index = p;
        }
    }

    return index;

}

Javascript 100%

const minAvgTwoSlice = (a) => {
if (a.length === 2) {
    return 0;
}

let avg;
let index;
for (let i = 0; i < a.length - 2; i++) {
    const val1 = a[i];
    const val2 = a[i + 1];
    const val3 = a[i + 2];
    const avg12 = (val1 + val2) / 2;
    const avg23 = (val2 + val3) / 2;
    const avg123 = (val1 + val2 + val3) / 3;

    if (typeof avg === 'undefined' || avg > avg12) {
        avg = avg12;
        index = i;
    }

    if (typeof avg === 'undefined' || avg > avg23) {
        avg = avg23;
        index = i + 1;
    }

    if (typeof avg === 'undefined' || avg > avg123) {
        avg = avg123;
        index = i;
    }
}

return index;
}

In Javascript - simple solution.

 function solution(A) {
      var sum, min = Infinity, idx=-1, avg=0;
      for(let p = 0; p < A.length; p++){
        sum = A[p];
        for(let q = p+1; q < p+4; q++){
          sum += A[q]
          avg = sum / (q-p+1)
          if(avg < min) {
            min = avg;
            idx=p;
          }
        }
      }
      return idx
 }