Find the minimal average of any slice containing at least two elements.
- Difficulty Level: Medium
- Question URL: https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/
- Time Complexity:
Solution:
Solution to Codility's Minimum Average Two Slice problem which is from the Codility Lesson 5: Prefix Sums and, is solved in Java 8 with 100% performance and correctness scores. The goal here is to find the minimal average of any slice containing at least two elements. You can find the question of this MinAvgTwoSlice problem in the Codility website.
package Codility.Lesson5;
import java.util.*;
public class MinAvgTwoSlice {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s = "CAGCCTA";
int[] in1 = { 2, 5, 0 };
int[] in2 = { 4, 5, 6 };
int result = solution(in2);
System.out.println(result);
}
public static 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;
}
}