Tasks Details
medium
Find the minimal average of any slice containing at least two elements.
Task Score
100%
Correctness
100%
Performance
100%
A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).
For example, array A such that:
A[0] = 4 A[1] = 2 A[2] = 2 A[3] = 5 A[4] = 1 A[5] = 5 A[6] = 8contains the following example slices:
- slice (1, 2), whose average is (2 + 2) / 2 = 2;
- slice (3, 4), whose average is (5 + 1) / 2 = 3;
- slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.
The goal is to find the starting position of a slice whose average is minimal.
Write a function:
class Solution { public int solution(int[] A); }
that, given a non-empty array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.
For example, given array A such that:
A[0] = 4 A[1] = 2 A[2] = 2 A[3] = 5 A[4] = 1 A[5] = 5 A[6] = 8the function should return 1, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [2..100,000];
- each element of array A is an integer within the range [−10,000..10,000].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 21
Time spent on task 13 minutes
Notes
not defined yet
Code: 02:08:17 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int len = A.length, result = len - 1;
double[] minimumAverages = createMinimumAverages(A);
double min = Double.MAX_VALUE;
for (int i = 0; i < len; ++i ) {
if( minimumAverages[i] < min ) {
min = minimumAverages[i];
result = i;
}
}
return result;
}
public double[] createMinimumAverages(int[] A) {
int len = A.length;
int[] prefixSums = new int[len];
for (int i = 1; i < len; ++i) {
prefixSums[i] = prefixSums[i-1] + A[i-1];
}
double[] minimumAverages = new double[len];
for ( int P = 0; P < len; ++P) {
double minAverage = Double.MAX_VALUE;
for (int Q = P + 1 ; Q < len; ++Q) {
int sum = prefixSums[Q + 1] - prefixSums[P];
double average = (sum)/(double) ( Q - P + 1 );
if( minAverage > average) {
minAverage = average;
}
}
minimumAverages[P] = minAverage;
}
return minimumAverages;
}
}
Analysis
expand all
Example tests
1.
1.363 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 7 at Solution.createMinimumAverages(Solution.java:34) at Solution.solution(Solution.java:10) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)
Code: 02:08:34 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int len = A.length, result = len - 1;
double[] minimumAverages = createMinimumAverages(A);
double min = Double.MAX_VALUE;
for (int i = 0; i < len; ++i ) {
if( minimumAverages[i] < min ) {
min = minimumAverages[i];
result = i;
}
}
return result;
}
public double[] createMinimumAverages(int[] A) {
int len = A.length;
int[] prefixSums = new int[len];
for (int i = 1; i <= len; ++i) {
prefixSums[i] = prefixSums[i-1] + A[i-1];
}
double[] minimumAverages = new double[len];
for ( int P = 0; P < len; ++P) {
double minAverage = Double.MAX_VALUE;
for (int Q = P + 1 ; Q < len; ++Q) {
int sum = prefixSums[Q + 1] - prefixSums[P];
double average = (sum)/(double) ( Q - P + 1 );
if( minAverage > average) {
minAverage = average;
}
}
minimumAverages[P] = minAverage;
}
return minimumAverages;
}
}
Analysis
expand all
Example tests
1.
1.331 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 7 at Solution.createMinimumAverages(Solution.java:27) at Solution.solution(Solution.java:10) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)
Code: 02:08:53 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int len = A.length, result = len - 1;
double[] minimumAverages = createMinimumAverages(A);
double min = Double.MAX_VALUE;
for (int i = 0; i < len; ++i ) {
if( minimumAverages[i] < min ) {
min = minimumAverages[i];
result = i;
}
}
return result;
}
public double[] createMinimumAverages(int[] A) {
int len = A.length;
int[] prefixSums = new int[len + 1];
for (int i = 1; i <= len; ++i) {
prefixSums[i] = prefixSums[i-1] + A[i-1];
}
double[] minimumAverages = new double[len];
for ( int P = 0; P < len; ++P) {
double minAverage = Double.MAX_VALUE;
for (int Q = P + 1 ; Q < len; ++Q) {
int sum = prefixSums[Q + 1] - prefixSums[P];
double average = (sum)/(double) ( Q - P + 1 );
if( minAverage > average) {
minAverage = average;
}
}
minimumAverages[P] = minAverage;
}
return minimumAverages;
}
}
Analysis
Code: 02:12:20 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int len = A.length, result = len - 1;
int[] prefixSums = new int[len + 1];
for (int i = 1; i <= len; ++i) {
prefixSums[i] = prefixSums[i-1] + A[i-1];
}
//double[] minimumAverages = createMinimumAverages(A);
double min = Double.MAX_VALUE;
for (int i = 0; i < len; ++i ) {
if( minimumAverages[i] < min ) {
min = minimumAverages[i];
result = i;
}
}
return result;
}
public double[] createMinimumAverages(int[] A) {
int len = A.length;
int[] prefixSums = new int[len + 1];
for (int i = 1; i <= len; ++i) {
prefixSums[i] = prefixSums[i-1] + A[i-1];
}
double[] minimumAverages = new double[len];
for ( int P = 0, Q = P + 1; P < len; ++P) {
double minAverage = Double.MAX_VALUE;
int sum = prefixSums[Q + 1] - prefixSums[P];
/*for (int Q = P + 1 ; Q < len; ++Q) {
int sum = prefixSums[Q + 1] - prefixSums[P];
double average = (sum)/(double) ( Q - P + 1 );
if( minAverage > average) {
minAverage = average;
}
}*/
minimumAverages[P] = minAverage;
}
return minimumAverages;
}
}
Analysis
Compile error
Solution.java:18: error: cannot find symbol
if( minimumAverages[i] < min ) {
^
symbol: variable minimumAverages
location: class Solution
Solution.java:19: error: cannot find symbol
min = minimumAverages[i];
^
symbol: variable minimumAverages
location: class Solution
2 errors
Code: 02:17:18 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int len = A.length, result = len - 1, sum = 0;
int[] prefixSums = new int[len + 1];
for (int i = 1; i <= len; ++i) {
prefixSums[i] = prefixSums[i-1] + A[i-1];
}
double min = Double.MAX_VALUE, average = 0d;
for (int P = 0, Q = 1, i = 0; Q < len; ++P ) {
sum = prefixSums[Q + 1] - prefixSums[P];
average = (sum)/(double) 2;
if (average < min) {
min = average;
i = P;
}
sum = prefixSums[Q + 2] - prefixSums[P];
average = (sum)/(double) 3;
if (average < min) {
min = average;
i = P;
}
}
return result;
}
}
Analysis
expand all
Example tests
1.
1.331 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 8 at Solution.solution(Solution.java:19) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)
Code: 02:17:57 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int len = A.length, result = len - 1, sum = 0;
int[] prefixSums = new int[len + 1];
for (int i = 1; i <= len; ++i) {
prefixSums[i] = prefixSums[i-1] + A[i-1];
}
double min = Double.MAX_VALUE, average = 0d;
for (int P = 0, Q = 1; Q < len; ++P ) {
sum = prefixSums[Q + 1] - prefixSums[P];
average = (sum)/(double) 2;
if (average < min) {
min = average;
result = P;
}
if ( Q + 2 < len ) {
sum = prefixSums[Q + 2] - prefixSums[P];
average = (sum)/(double) 3;
if (average < min) {
min = average;
result = P;
}
}
}
return result;
}
}
Analysis
expand all
Example tests
1.
1.356 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 8 at Solution.solution(Solution.java:19) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)
Code: 02:18:12 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int len = A.length, result = len - 1, sum = 0;
int[] prefixSums = new int[len + 1];
for (int i = 1; i <= len; ++i) {
prefixSums[i] = prefixSums[i-1] + A[i-1];
}
double min = Double.MAX_VALUE, average = 0d;
for (int P = 0, Q = 1; Q < len; ++P ) {
sum = prefixSums[Q + 1] - prefixSums[P];
average = (sum)/(double) 2;
if (average < min) {
min = average;
result = P;
}
if ( Q + 2 < prefixSums.length ) {
sum = prefixSums[Q + 2] - prefixSums[P];
average = (sum)/(double) 3;
if (average < min) {
min = average;
result = P;
}
}
}
return result;
}
}
Analysis
expand all
Example tests
1.
1.334 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 8 at Solution.solution(Solution.java:19) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)
Code: 02:18:36 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int len = A.length, result = len - 1, sum = 0;
int[] prefixSums = new int[len + 1];
for (int i = 1; i <= len; ++i) {
prefixSums[i] = prefixSums[i-1] + A[i-1];
}
double min = Double.MAX_VALUE, average = 0d;
for (int P = 0, Q = 1; Q < prefixSums.length; ++P ) {
sum = prefixSums[Q + 1] - prefixSums[P];
average = (sum)/(double) 2;
if (average < min) {
min = average;
result = P;
}
if ( Q + 2 < prefixSums.length ) {
sum = prefixSums[Q + 2] - prefixSums[P];
average = (sum)/(double) 3;
if (average < min) {
min = average;
result = P;
}
}
}
return result;
}
}
Analysis
expand all
Example tests
1.
1.010 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 8 at Solution.solution(Solution.java:19) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)
Code: 02:18:53 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int len = A.length, result = len - 1, sum = 0;
int[] prefixSums = new int[len + 1];
for (int i = 1; i <= len; ++i) {
prefixSums[i] = prefixSums[i-1] + A[i-1];
}
double min = Double.MAX_VALUE, average = 0d;
for (int P = 0, Q = 1; Q + 1 < prefixSums.length; ++P ) {
sum = prefixSums[Q + 1] - prefixSums[P];
average = (sum)/(double) 2;
if (average < min) {
min = average;
result = P;
}
if ( Q + 2 < prefixSums.length ) {
sum = prefixSums[Q + 2] - prefixSums[P];
average = (sum)/(double) 3;
if (average < min) {
min = average;
result = P;
}
}
}
return result;
}
}
Analysis
expand all
Example tests
1.
1.605 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 8 at Solution.solution(Solution.java:19) at wrapper.run(wrapper.java:40) at wrapper.main(wrapper.java:29)
Code: 02:19:50 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
int len = A.length, result = len - 1, sum = 0;
int[] prefixSums = new int[len + 1];
for (int i = 1; i <= len; ++i) {
prefixSums[i] = prefixSums[i-1] + A[i-1];
}
double min = Double.MAX_VALUE, average = 0d;
for (int P = 0, Q = 1; Q + 1 < prefixSums.length; ++P, ++Q ) {
sum = prefixSums[Q + 1] - prefixSums[P];
average = (sum)/(double) 2;
if (average < min) {
min = average;
result = P;
}
if ( Q + 2 < prefixSums.length ) {
sum = prefixSums[Q + 2] - prefixSums[P];
average = (sum)/(double) 3;
if (average < min) {
min = average;
result = P;
}
}
}
return result;
}
}
Analysis
Code: 02:20:18 UTC,
java,
verify,
result: Passed
class Solution {
public int solution(int[] A) {
int len = A.length, result = len - 1, sum = 0;
int[] prefixSums = new int[len + 1];
for (int i = 1; i <= len; ++i) {
prefixSums[i] = prefixSums[i-1] + A[i-1];
}
double min = Double.MAX_VALUE, average = 0d;
for (int P = 0, Q = 1; Q + 1 < prefixSums.length; ++P, ++Q ) {
sum = prefixSums[Q + 1] - prefixSums[P];
average = (sum)/(double) 2;
if (average < min) {
min = average;
result = P;
}
if ( Q + 2 < prefixSums.length ) {
sum = prefixSums[Q + 2] - prefixSums[P];
average = (sum)/(double) 3;
if (average < min) {
min = average;
result = P;
}
}
}
return result;
}
}
Analysis
Code: 02:20:34 UTC,
java,
verify,
result: Passed
class Solution {
public int solution(int[] A) {
int len = A.length, result = len - 1, sum = 0;
int[] prefixSums = new int[len + 1];
for (int i = 1; i <= len; ++i) {
prefixSums[i] = prefixSums[i-1] + A[i-1];
}
double min = Double.MAX_VALUE, average = 0d;
for (int P = 0, Q = 1; Q + 1 < prefixSums.length; ++P, ++Q ) {
sum = prefixSums[Q + 1] - prefixSums[P];
average = (sum)/(double) 2;
if (average < min) {
min = average;
result = P;
}
if ( Q + 2 < prefixSums.length ) {
sum = prefixSums[Q + 2] - prefixSums[P];
average = (sum)/(double) 3;
if (average < min) {
min = average;
result = P;
}
}
}
return result;
}
}
Analysis
Code: 02:20:39 UTC,
java,
final,
score:
100
class Solution {
public int solution(int[] A) {
int len = A.length, result = len - 1, sum = 0;
int[] prefixSums = new int[len + 1];
for (int i = 1; i <= len; ++i) {
prefixSums[i] = prefixSums[i-1] + A[i-1];
}
double min = Double.MAX_VALUE, average = 0d;
for (int P = 0, Q = 1; Q + 1 < prefixSums.length; ++P, ++Q ) {
sum = prefixSums[Q + 1] - prefixSums[P];
average = (sum)/(double) 2;
if (average < min) {
min = average;
result = P;
}
if ( Q + 2 < prefixSums.length ) {
sum = prefixSums[Q + 2] - prefixSums[P];
average = (sum)/(double) 3;
if (average < min) {
min = average;
result = P;
}
}
}
return result;
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
1.315 s
OK
2.
1.317 s
OK
3.
1.321 s
OK
4.
1.317 s
OK
1.
1.319 s
OK
2.
1.310 s
OK
1.
1.315 s
OK
1.
1.326 s
OK
1.
1.312 s
OK
2.
1.315 s
OK
3.
1.329 s
OK
expand all
Performance tests
1.
1.327 s
OK
1.
1.499 s
OK
2.
1.453 s
OK
1.
1.556 s
OK
1.
1.580 s
OK
2.
1.574 s
OK
3.
1.576 s
OK
1.
1.476 s
OK
2.
1.446 s
OK