MinAvgTwoSlice – Codility – Solution

Java solution to Codility MinAvgTwoSlice problem (Lesson 5 – Prefix Sums) which scored 100%. The problem is to find the minimal average of any slice containing at least two elements. The strategy is to find the minimum average by checking only 2 and 3 contiguous elements at a time.

References
Solution to Min-Avg-Two-Slice – Code Says (Python)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package com.codility.lesson05.prefixsums;

public class MinAverageTwoSlice {
  public int solution(int[] A) {

    //main idea: will find min average by checking only 2 and 3 contiguous elements at a time
    int sum1, sum2 = 0;
    double minAverage = Double.MAX_VALUE;
    double currentAverage1 = Double.MAX_VALUE;
    double currentAverage2 = Double.MAX_VALUE;
    int minAverageSliceIndex = 0; //for size 2 arrays, this will always be true

    //if array is > 2 elements
    for(int i=0; i<A.length-2; i++) {
      sum1 = A[i] + A[i+1];
      currentAverage1 = sum1 / 2.0d;
      if(currentAverage1 < minAverage) {
        minAverage = currentAverage1;
        minAverageSliceIndex = i;
      }

      sum2 = sum1 + A[i+2];
      currentAverage2 = sum2 / 3.0d;
      if(currentAverage2 < minAverage) {
        minAverage = currentAverage2;
        minAverageSliceIndex = i;
      }
    }

    //check last 2 contiguous elements from the end - they won't otherwise be checked because
    //when checking 2 and 3 contiguous elements at a time, will stop checking 3 elements from the end
    currentAverage1 = (A[A.length-2] + A[A.length-1]) / 2.0d;
    if(currentAverage1 < minAverage) {
      minAverage = currentAverage1;
      minAverageSliceIndex = A.length-2;
    }
   
    return minAverageSliceIndex;
  }
}

TestNG test cases for this problem which all passed:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package test.com.codility.lesson05.prefixsums;

import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

import com.codility.lesson05.prefixsums.MinAverageTwoSlice;

public class MinAverageTwoSliceTests {
  private MinAverageTwoSlice solution;
 
  @BeforeTest
  public void setUp() {
    solution = new MinAverageTwoSlice();
  }

  @DataProvider(name = "test1")
  public Object [][] createData1() {
    return new Object [][] {
      new Object [] {  new int [] { 4, 2, 2, 5, 1, 5, 8 }, 1 },
      new Object [] {  new int [] { 10000, -10000 }, 0 }
    };
  }

  @Test(dataProvider = "test1")
  public void verifySolution(int [] pA, int pExpected) {   
    Assert.assertEquals(solution.solution(pA), pExpected);
  }  
}