Codility ‘MinAvgTwoSlice’ Solution

Short Problem Definition:

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

Link

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

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin