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)
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
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:
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
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);
}
}