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)

[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]