Lesson 3: MinAvgTwoSlice (Min Avg Two Slice)

This problem is indeed a math question. 

To check the number of the slots that produce the minimum average, we only have to check the sum of the consecutive two or three slots.

Think of the case in which there are the slice made of four slots. Let's assume these four slots can produce the minimum average. 

The slice can be decomposed into two pairs, each of which consists two slots. If any of these pairs can produce a smaller average than the original four slots, then it contradicts the first assumption. If they produce a bigger average, then the other pair must be smaller than the average of the original four slots. So will be the same value. The same can be said to 5 slots (2+3), etc.

This can be said to any slice of an arbitrary size. If any sub-slice of a certain slice can produce a smaller average, then the original slice is not the slice that can produce a smaller portion. It the average values of the original slice and sub-slice are the same, we can simply take the index where the original slice starts, since what we need to return is the smallest index.

The below code implements this strategy and returns the score of 100%.

int solution(int A[], int N) 
{
    int i = 0;
    
    if (N == 2){
        return 0;
    }

    //initialize the current minimum average of the first two slots.
    double minavg = (A[0] + A[1]) / 2.0;
    int idx = 0;
    

    for (i = 2; i < N; i++){
        double tmp1 = (A[i - 1] + A[i]) / 2.0;
        double tmp2 = (A[i - 2] + A[i - 1] + A[i]) / 3.0;
        
        if (tmp1 < minavg){
            idx = i - 1;
            minavg = tmp1;
        }
        if (tmp2 < minavg){
            idx = i - 2;
            minavg = tmp2;
        }
    }
    return idx;
}