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)
[cc lang="java" escaped="true"] 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; } } [/cc]
TestNG test cases for this problem which all passed:
[cc lang="java" escaped="true"] 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); } } [/cc]