# Codility 'MinAvgTwoSlice' Solution

Martin Kysel · January 2, 2015

##### Short Problem Definition:

Find the minimal average of any slice containing at least two elements.

MinAvgTwoSlice

##### Complexity:

expected worst-case time complexity is `O(N)`

expected worst-case space complexity is `O(N)`

##### Execution:

Every slice must be of size two or three. Slices of bigger sizes are created from such smaller slices. Therefore should any bigger slice have an optimal value, all sub-slices must be the same, for this case to hold true. Should this not be true, one of the sub-slices must be the optimal slice. The others being bigger. Therefore we check all possible slices of size 2/3 and return the smallest one. The first such slice is the correct one, do not use <=!

For other languages use BigInts or equal. This line (A[idx] + A[idx+1] + A[idx+2])/3.0 can easily overflow!

You can read the formal proof by Minh Tran Dao here.

##### Solution:
``````
def solution(A):
min_idx = 0
min_value = 10001

for idx in xrange(0, len(A)-1):
if (A[idx] + A[idx+1])/2.0 < min_value:
min_idx = idx
min_value = (A[idx] + A[idx+1])/2.0
if idx < len(A)-2 and (A[idx] + A[idx+1] + A[idx+2])/3.0 < min_value:
min_idx = idx
min_value = (A[idx] + A[idx+1] + A[idx+2])/3.0

return min_idx
``````