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
  • mijhael castro civiero

    Hi Martin,

    I think your solution is just valid for your assumptions about slices of 2 and 3 element size. But I do not see any assumption regarding the size of the slice on the codility exercise. Even they take this slice formed with 4 elements:
    A= [4, 2, 2, 5, 1, 5, 8]
    A(1, 4), which have an average of (2 + 2 + 5 + 1) / 4 = 2.5

    So if we have an array like this:
    A=[0, 8, 0, 0, -8, 0]
    the slice with the min avg is:
    A(1,4)=0
    and your code returns:3
    How could this result be valid?

    I enjoy reading your post solutions! They are well explained!

    Thanks.

    Cheers.

    • Hi Mijhael,

      the slice A(1,4) has an average of 2.5. The slice A(1,2) has an average of 2. That is better, isn’t it?

      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. All other slices will have worse average than the 4 element slice.

      As for the second case. There are two optimal slices. A(3,4) = (0 – 8)/ 2 = -4 and A(4,5) = (0 – 8)/ 2 = -4. The other ones are worse, for example A(3,4,5) = (0-8+0)/3 = – 2,666.

      Notice that you return the INDEX of the smallest possible slice. Not the actual value.

      • mijhael castro civiero

        I appreciate your answer.
        Very clear.

        Cheers!

        • Richard Yang

          I don’t know how you can deduce this assertion. It’s really hard to reason this problem like you. Could you tell me what’s the process you think of the solution?

          • Sure.

            The problem is categorized as “Prefix sums”, which is kinda misleading, because the optimal solution does not use prefix sums… After I realized that, I started brainstorming other solutions. It did not look like a DP problem as it did not have solvable sub-problems; binary search seemed reasonable but O(n) would not work;

            After that I came back to the prefix sums. You can easily adapt the average if you know the number of elements, and the previous average (prefix sum). From this point on, you can try to find a solution that only adds new elements to an sub-slice if the average gets better, or restarts the sub-slice. Think of the caterpillar method. At this point you have to define your edge cases, starting with the smallest possible cases (1,2,3). This led to me to realization, that you actually only need to consider slices of length 2 and 3. If a slice of length 1 was allowed, the minimal element would be optimal.

          • Richard Yang

            Nice. Thank you, Martin. I learnt a lot from you. More often, the thought is more important than a specific problem. I completely agree that this problem should not be categorised in “Prefix sums” as a task to practice.

  • Here’s my solution in Scala http://geeks.aretotally.in/codility-minavgtwoslice-in-scala/

    object Solution {
    def solution(A: Array[Int]): Int = {

    (A.foldLeft[(Int, Option[Double], Int)]((0, None, -1)) { (t, item) =>
    val (index, min, results) = t

    val checkPair = index <= A.size – 2
    val checkTrio = index (A(index) + A(index + 1)) / 2.0 }
    val trioMin = checkSlice(min, checkTrio) { () => (A(index) + A(index + 1) + A(index + 2)) / 3.0 }

    if (pairMin.isDefined || trioMin.isDefined) (index + 1, Some(Math.min(pairMin.getOrElse(Double.MaxValue), trioMin.getOrElse(Double.MaxValue))), index)
    else (index + 1, min, results)
    })._3
    }

    def checkSlice(min: Option[Double], check: Boolean)(f: () => Double) = {
    check match {
    case true =>
    val value = f()
    min map { minValue =>
    if (value
    None
    }
    }
    }

  • Mike Copeland

    Did this solution get you 100% on Codility? I ask because my solution was only getting 80%, so I have just translated this algorithm into Java and put it into Codility and it got a lower score (70%) than my own solution.

    I’m no expert in Python but I can’t see any difference between my Java implementation and the Python one you give. Here is my Java translation:

    public int solution(int[] A) {
    double minAvg = Double.MAX_VALUE;
    int minIdx = 0;

    for(int i = 0; i < A.length – 1; i++) {
    final double twoSlice = (double)A[i] + A[i + 1] / 2;
    if(twoSlice < minAvg) {
    minAvg = twoSlice;
    minIdx = i;
    }
    if(i < A.length – 2) {
    final double threeSlice = (double)A[i] + A[i + 1] + A[i + 2] / 3;
    if(threeSlice < minAvg) {
    minAvg = threeSlice;
    minIdx = i;
    }
    }
    }

    return minIdx;
    }

  • Deniz Kennedy

    Hi Martin,

    The solution is really nice and clever. Do you happen to know the name of this method or any mathematical proof that shows this specific method will be valid for all cases?

    • Hi Deniz,
      I have too little knowledge in mathematical proofs to be any useful :). In programming terms it is ‘Simplify and Generalize’.

      • Deniz Kennedy

        OK, thanks a lot 🙂

  • Pavel Llamocca Portella

    Hi.. My solution is not the optimal, It fails :(.
    But I have a doubt. One test case in codility for this exercise is [5, 6, 3, 4, 9]. And, the error message for my code is : (got 1 expected 2).
    So. I think I have a misunderstanding about what an slice is. For that example. my slices are:
    0 2 (avg = 4.666..)
    0 3 (avg = 4.5)
    0 4 (avg = 5.4)
    1 3 (avg= 4.3333..)
    1 4 (avg=5.5)
    2 4 (avg=5.33…)
    In base of the only condition to be a slice “0 ≤ P < Q < N". All my slices satisfied this condition isnt?. So the answer should be 1 (avg:4.333)

    • Two things: the slice can be of 2 elements as well. 0-1, 1-2, 2-3 etc.

      Just by looking at the elements the smallest average of two elements is 3+4/2 = 3.5; Three is at index 2, which is the correct answer. No slice starting at 1 (6+3/2=4.5, 6+3+4/3=4.333, 6+3+4+9/4=5.5) is smaller

  • salmAn

    About the math behind the solution. Let e.g. C denote the avg of a slice of size 5: C=(v+w+x+y+z)/5. And let A and B denote the avg of corresponding slices of size 2 and 3, respectively, i.e., A=(v+w)/2 and B=(x+y+z)/3.
    Simple math shows: C = 0.4*A+0.6*B.
    Claim: it cannot be that C<A and C<B at the same time.
    Proof. Let say this is the case. Then we have 0.4*C<0.4*A, and 0.6*C<0.6*B. Summing these two, we get 0.4*C+0.6*C<0.4*A+0.6*B, or equivalently C<C, which is obviously wrong.
    Therefore, either A <=C or B<=C. But, the algorithm already returns the best of A and B, thus the algorithm is also handling slices of size 5.
    For slices of bigger size, we can reason similarly.

    • salmAn

      Do you guys see my post completely, or only partly as I see?!

      • here a screenshot (the best way to talk about visual stuff)

        • salmAn

          That’s incomplete! I wrote this:

    • I’ve updated your comment. DISQUS does not like smaller than signs followed by a number. It interprets them as HTML. It seems that you need a space after “<"

      • salmAn

        Very good, thanks a lot!

  • About the math behind the solution. Let e.g. C denote the avg of a slice of size 5: C=(v+w+x+y+z)/5. And let A and B denote the avg of corresponding slices of size 2 and 3, respectively, i.e., A=(v+w)/2 and B=(x+y+z)/3.
    Simple math shows: C = 0.4*A+0.6*B.
    Claim: it cannot be that C < A and C < B at the same time.
    Proof. Let say this is the case. Then we have 0.4*C < 0.4*A, and 0.6*C < 0.6*B. Summing these two, we get 0.4*C+0.6*C < 0.4*A+0.6*B, or equivalently C < C, which is obviously wrong.
    Therefore, either A <=C or B<=C. But, the algorithm already returns the best of A and B, thus the algorithm is also handling slices of size 5.
    For slices of bigger size, we can reason similarly.

  • Minh Tran Dao

    Thanks a lot for the observation. I did a formal proof here https://github.com/daotranminh/playground/blob/master/src/codibility/MinAvgTwoSlice/proof.pdf. As I finished and looked at the comments, salmAn had a similar proof. I just approached it in a more general way.

  • sameer karode

    Hi martin,
    Can u please explain why you have not considered size of slices beyond 2 and 3 ?

  • Jiří Lechner

    I think your solution is wrong. You find a slice with the minimal arithmetical average but not with the smallest starting index. That actually may be a slice of a bigger length since arithmetical average of a subslice of size 2 or 3 is smaller or equal to the average of the original one…