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:
object Solution { def solution(a: Array[Int]): Int }
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 Scala
Time spent on task 59 minutes
Notes
not defined yet
Task timeline
Code: 19:44:18 UTC,
scala,
verify,
result: Failed
import scala.collection.JavaConversions._
// you can use println for debugging purposes, e.g.
// println("this is a debug message")
object Solution {
def solution(A: Array[Int]): Int = {
@scala.annotation.tailrec
def loop(index: Int): Int = {
if (index >= A.length - 1) 0
else loop(index + 1)
}
loop(0)
}
}
Analysis
expand all
Example tests
1.
1.979 s
WRONG ANSWER,
got 0 expected 1
Code: 19:51:50 UTC,
scala,
verify,
result: Failed
import scala.collection.JavaConversions._
// you can use println for debugging purposes, e.g.
// println("this is a debug message")
object Solution {
def solution(A: Array[Int]): Int = {
@scala.annotation.tailrec
def loop(index: Int, curMinIdx: Int, curMinAvg: Double): Int = {
if (index >= A.length - 1) 0
else {
val pairAvg = (A(index) + A(index + 1)).toDouble / 2
val trioAvg = (pairAvg * 2 / 3) + (A(index + 2).toDouble / 3)
val minAtIdx = pairAvg min trioAvg
if (minAtIdx < curMinIdx)
loop(index + 1, index, minAtIdx)
else
loop(index + 1, curMinIdx, curMinAvg)
}
}
loop(0, 0, Double.MaxValue)
}
}
Analysis
expand all
Example tests
1.
2.280 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 7 at Solution$.loop$1(Solution.scala:16) at Solution$.solution(Solution.scala:25) at Wrapper$.run(user.scala:31) at Wrapper$.main(user.scala:24) at Wrapper.main(user.scala)
Code: 19:52:09 UTC,
scala,
verify,
result: Failed
import scala.collection.JavaConversions._
// you can use println for debugging purposes, e.g.
// println("this is a debug message")
object Solution {
def solution(A: Array[Int]): Int = {
@scala.annotation.tailrec
def loop(index: Int, curMinIdx: Int, curMinAvg: Double): Int = {
if (index >= A.length - 2) 0
else {
val pairAvg = (A(index) + A(index + 1)).toDouble / 2
val trioAvg = (pairAvg * 2 / 3) + (A(index + 2).toDouble / 3)
val minAtIdx = pairAvg min trioAvg
if (minAtIdx < curMinIdx)
loop(index + 1, index, minAtIdx)
else
loop(index + 1, curMinIdx, curMinAvg)
}
}
loop(0, 0, Double.MaxValue)
}
}
Analysis
expand all
Example tests
1.
2.642 s
WRONG ANSWER,
got 0 expected 1
Code: 19:52:22 UTC,
scala,
verify,
result: Failed
import scala.collection.JavaConversions._
// you can use println for debugging purposes, e.g.
// println("this is a debug message")
object Solution {
def solution(A: Array[Int]): Int = {
@scala.annotation.tailrec
def loop(index: Int, curMinIdx: Int, curMinAvg: Double): Int = {
if (index >= A.length - 2) curMinIdx
else {
val pairAvg = (A(index) + A(index + 1)).toDouble / 2
val trioAvg = (pairAvg * 2 / 3) + (A(index + 2).toDouble / 3)
val minAtIdx = pairAvg min trioAvg
if (minAtIdx < curMinIdx)
loop(index + 1, index, minAtIdx)
else
loop(index + 1, curMinIdx, curMinAvg)
}
}
loop(0, 0, Double.MaxValue)
}
}
Analysis
expand all
Example tests
1.
2.265 s
WRONG ANSWER,
got 0 expected 1
Code: 19:53:26 UTC,
scala,
verify,
result: Failed
import scala.collection.JavaConversions._
// you can use println for debugging purposes, e.g.
// println("this is a debug message")
object Solution {
def solution(A: Array[Int]): Int = {
@scala.annotation.tailrec
def loop(index: Int, curMinIdx: Int, curMinAvg: Double): Int = {
if (index >= A.length - 2) curMinIdx
else {
val pairAvg = (A(index) + A(index + 1)).toDouble / 2
println(s"idx=$index,pairAvg=$pairAvg,trioAvg=$trioAvg")
val trioAvg = (pairAvg * 2 / 3) + (A(index + 2).toDouble / 3)
val minAtIdx = pairAvg min trioAvg
if (minAtIdx < curMinIdx)
loop(index + 1, index, minAtIdx)
else
loop(index + 1, curMinIdx, curMinAvg)
}
}
loop(0, 0, Double.MaxValue)
}
}
Analysis
Compile error
Solution.scala:14: error: forward reference extends over definition of value trioAvg
println(s"idx=$index,pairAvg=$pairAvg,trioAvg=$trioAvg")
^
one error found
Code: 19:53:51 UTC,
scala,
verify,
result: Failed
import scala.collection.JavaConversions._
// you can use println for debugging purposes, e.g.
// println("this is a debug message")
object Solution {
def solution(A: Array[Int]): Int = {
@scala.annotation.tailrec
def loop(index: Int, curMinIdx: Int, curMinAvg: Double): Int = {
if (index >= A.length - 2) curMinIdx
else {
val pairAvg = (A(index) + A(index + 1)).toDouble / 2
println(s"idx=$index,pairAvg=$pairAvg,trioAvg=$trioAvg")
val trioAvg = (pairAvg * 2 / 3) + (A(index + 2).toDouble / 3)
println(s"idx=$index,pairAvg=$pairAvg,trioAvg=$trioAvg")
val minAtIdx = pairAvg min trioAvg
if (minAtIdx < curMinIdx)
loop(index + 1, index, minAtIdx)
else
loop(index + 1, curMinIdx, curMinAvg)
}
}
loop(0, 0, Double.MaxValue)
}
}
Analysis
Compile error
Solution.scala:14: error: forward reference extends over definition of value trioAvg
println(s"idx=$index,pairAvg=$pairAvg,trioAvg=$trioAvg")
^
one error found
Code: 19:54:10 UTC,
scala,
verify,
result: Failed
import scala.collection.JavaConversions._
// you can use println for debugging purposes, e.g.
// println("this is a debug message")
object Solution {
def solution(A: Array[Int]): Int = {
@scala.annotation.tailrec
def loop(index: Int, curMinIdx: Int, curMinAvg: Double): Int = {
if (index >= A.length - 2) curMinIdx
else {
val pairAvg = (A(index) + A(index + 1)).toDouble / 2
val trioAvg = (pairAvg * 2 / 3) + (A(index + 2).toDouble / 3)
println(s"idx=$index,pairAvg=$pairAvg,trioAvg=$trioAvg")
val minAtIdx = pairAvg min trioAvg
if (minAtIdx < curMinIdx)
loop(index + 1, index, minAtIdx)
else
loop(index + 1, curMinIdx, curMinAvg)
}
}
loop(0, 0, Double.MaxValue)
}
}
Analysis
expand all
Example tests
1.
2.332 s
WRONG ANSWER,
got 0 expected 1
stdout:
idx=0,pairAvg=3.0,trioAvg=2.6666666666666665 idx=1,pairAvg=2.0,trioAvg=3.0 idx=2,pairAvg=3.5,trioAvg=2.666666666666667 idx=3,pairAvg=3.0,trioAvg=3.666666666666667 idx=4,pairAvg=3.0,trioAvg=4.666666666666666
Code: 19:57:22 UTC,
scala,
verify,
result: Failed
import scala.collection.JavaConversions._
// you can use println for debugging purposes, e.g.
// println("this is a debug message")
object Solution {
def solution(A: Array[Int]): Int = {
@scala.annotation.tailrec
def loop(index: Int, curMinIdx: Int, curMinAvg: Double): Int = {
if (index >= A.length - 2) curMinIdx
else {
val pairAvg = (A(index) + A(index + 1)).toDouble / 2
val trioAvg = (pairAvg * 2 / 3) + (A(index + 2).toDouble / 3)
println(s"idx=$index,pairAvg=$pairAvg,trioAvg=$trioAvg")
val minAtIdx = pairAvg min trioAvg
println(s"curMinIdx=$curMinIdx,curMinAvg=$curMinAvg,minAtIdx=$minAtIdx")
if (minAtIdx < curMinIdx)
loop(index + 1, index, minAtIdx)
else
loop(index + 1, curMinIdx, curMinAvg)
}
}
loop(0, 0, Double.MaxValue)
}
}
Analysis
expand all
Example tests
1.
2.344 s
WRONG ANSWER,
got 0 expected 1
stdout:
idx=0,pairAvg=3.0,trioAvg=2.6666666666666665 curMinIdx=0,curMinAvg=1.7976931348623157E308,minAtIdx=2.6666666666666665 idx=1,pairAvg=2.0,trioAvg=3.0 curMinIdx=0,curMinAvg=1.7976931348623157E308,minAtIdx=2.0 idx=2,pairAvg=3.5,trioAvg=2.666666666666667 curMinIdx=0,curMinAvg=1.7976931348623157E308,minAtIdx=2.666666666666667 idx=3,pairAvg=3.0,trioAvg=3.666666666666667 curMinIdx=0,curMinAvg=1.7976931348623157E308,minAtIdx=3.0 idx=4,pairAvg=3.0,trioAvg=4.666666666666666 curMinIdx=0,curMinAvg=1.7976931348623157E308,minAtIdx=3.0
Code: 20:01:03 UTC,
scala,
verify,
result: Failed
import scala.collection.JavaConversions._
// you can use println for debugging purposes, e.g.
// println("this is a debug message")
object Solution {
def solution(A: Array[Int]): Int = {
@scala.annotation.tailrec
def loop(index: Int, curMinIdx: Int, curMinAvg: Double): Int = {
if (index >= A.length - 2) curMinIdx
else {
val pairAvg = (A(index) + A(index + 1)).toDouble / 2
val trioAvg = (pairAvg * 2 / 3) + (A(index + 2).toDouble / 3)
println(s"idx=$index,pairAvg=$pairAvg,trioAvg=$trioAvg")
val minAtIdx = pairAvg min trioAvg
println(s"curMinIdx=$curMinIdx,curMinAvg=$curMinAvg,minAtIdx=$minAtIdx")
if (minAtIdx < curMinIdx) {
println("lower")
loop(index + 1, index, minAtIdx)
} else {
println("higher")
loop(index + 1, curMinIdx, curMinAvg)
}
}
}
loop(0, 0, Double.MaxValue)
}
}
Analysis
expand all
Example tests
1.
1.891 s
WRONG ANSWER,
got 0 expected 1
stdout:
idx=0,pairAvg=3.0,trioAvg=2.6666666666666665 curMinIdx=0,curMinAvg=1.7976931348623157E308,minAtIdx=2.6666666666666665 higher idx=1,pairAvg=2.0,trioAvg=3.0 curMinIdx=0,curMinAvg=1.7976931348623157E308,minAtIdx=2.0 higher idx=2,pairAvg=3.5,trioAvg=2.666666666666667 curMinIdx=0,curMinAvg=1.7976931348623157E308,minAtIdx=2.666666666666667 higher idx=3,pairAvg=3.0,trioAvg=3.666666666666667 curMinIdx=0,curMinAvg=1.7976931348623157E308,minAtIdx=3.0 higher idx=4,pairAvg=3.0,trioAvg=4.666666666666666 curMinIdx=0,curMinAvg=1.7976931348623157E308,minAtIdx=3.0 higher
Code: 20:01:35 UTC,
scala,
verify,
result: Passed
import scala.collection.JavaConversions._
// you can use println for debugging purposes, e.g.
// println("this is a debug message")
object Solution {
def solution(A: Array[Int]): Int = {
@scala.annotation.tailrec
def loop(index: Int, curMinIdx: Int, curMinAvg: Double): Int = {
if (index >= A.length - 2) curMinIdx
else {
val pairAvg = (A(index) + A(index + 1)).toDouble / 2
val trioAvg = (pairAvg * 2 / 3) + (A(index + 2).toDouble / 3)
println(s"idx=$index,pairAvg=$pairAvg,trioAvg=$trioAvg")
val minAtIdx = pairAvg min trioAvg
println(s"curMinIdx=$curMinIdx,curMinAvg=$curMinAvg,minAtIdx=$minAtIdx")
if (minAtIdx < curMinAvg) {
println("lower")
loop(index + 1, index, minAtIdx)
} else {
println("higher")
loop(index + 1, curMinIdx, curMinAvg)
}
}
}
loop(0, 0, Double.MaxValue)
}
}
Analysis
expand all
Example tests
1.
1.867 s
OK
stdout:
idx=0,pairAvg=3.0,trioAvg=2.6666666666666665 curMinIdx=0,curMinAvg=1.7976931348623157E308,minAtIdx=2.6666666666666665 lower idx=1,pairAvg=2.0,trioAvg=3.0 curMinIdx=0,curMinAvg=2.6666666666666665,minAtIdx=2.0 lower idx=2,pairAvg=3.5,trioAvg=2.666666666666667 curMinIdx=1,curMinAvg=2.0,minAtIdx=2.666666666666667 higher idx=3,pairAvg=3.0,trioAvg=3.666666666666667 curMinIdx=1,curMinAvg=2.0,minAtIdx=3.0 higher idx=4,pairAvg=3.0,trioAvg=4.666666666666666 curMinIdx=1,curMinAvg=2.0,minAtIdx=3.0 higher
Code: 20:03:50 UTC,
scala,
verify,
result: Passed
import scala.collection.JavaConversions._
// you can use println for debugging purposes, e.g.
// println("this is a debug message")
object Solution {
def solution(A: Array[Int]): Int = {
@scala.annotation.tailrec
def loop(index: Int, curMinIdx: Int, curMinAvg: Double): Int = {
if (index >= A.length - 1) curMinIdx
else {
val pairAvg = (A(index) + A(index + 1)).toDouble / 2
val minAtIdx = {
if (index >= A.length - 2) pairAvg
else {
val trioAvg = (pairAvg * 2 / 3) + (A(index + 2).toDouble / 3)
pairAvg min trioAvg
}
}
if (minAtIdx < curMinAvg) {
loop(index + 1, index, minAtIdx)
} else {
loop(index + 1, curMinIdx, curMinAvg)
}
}
}
loop(0, 0, Double.MaxValue)
}
}
Analysis
Code: 20:05:32 UTC,
scala,
verify,
result: Passed
import scala.collection.JavaConversions._
// you can use println for debugging purposes, e.g.
// println("this is a debug message")
object Solution {
def solution(A: Array[Int]): Int = {
@scala.annotation.tailrec
def loop(index: Int, curMinIdx: Int, curMinAvg: Double): Int = {
if (index >= A.length - 1) curMinIdx
else {
val pairAvg = (A(index) + A(index + 1)).toDouble / 2
val minAtIdx = {
if (index >= A.length - 2) pairAvg
else {
val trioAvg = (2 * pairAvg + A(index + 2)).toDouble / 3
pairAvg min trioAvg
}
}
if (minAtIdx < curMinAvg) {
loop(index + 1, index, minAtIdx)
} else {
loop(index + 1, curMinIdx, curMinAvg)
}
}
}
loop(0, 0, Double.MaxValue)
}
}
Analysis
Code: 20:06:51 UTC,
scala,
verify,
result: Passed
import scala.collection.JavaConversions._
// you can use println for debugging purposes, e.g.
// println("this is a debug message")
object Solution {
def solution(A: Array[Int]): Int = {
@scala.annotation.tailrec
def loop(index: Int, curMinIdx: Int, curMinAvg: Double): Int = {
if (index >= A.length - 1) curMinIdx
else {
val pairAvg = (A(index) + A(index + 1)).toDouble / 2
val minAtIdx = {
if (index >= A.length - 2) pairAvg
else {
val trioAvg = (2 * pairAvg + A(index + 2)).toDouble / 3
pairAvg min trioAvg
}
}
if (minAtIdx < curMinAvg) {
loop(index + 1, index, minAtIdx)
} else {
loop(index + 1, curMinIdx, curMinAvg)
}
}
}
loop(0, 0, Double.MaxValue)
}
}
Analysis
Code: 20:07:12 UTC,
scala,
final,
score:
100
import scala.collection.JavaConversions._
// you can use println for debugging purposes, e.g.
// println("this is a debug message")
object Solution {
def solution(A: Array[Int]): Int = {
@scala.annotation.tailrec
def loop(index: Int, curMinIdx: Int, curMinAvg: Double): Int = {
if (index >= A.length - 1) curMinIdx
else {
val pairAvg = (A(index) + A(index + 1)).toDouble / 2
val minAtIdx = {
if (index >= A.length - 2) pairAvg
else {
val trioAvg = (2 * pairAvg + A(index + 2)).toDouble / 3
pairAvg min trioAvg
}
}
if (minAtIdx < curMinAvg) {
loop(index + 1, index, minAtIdx)
} else {
loop(index + 1, curMinIdx, curMinAvg)
}
}
}
loop(0, 0, Double.MaxValue)
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
2.242 s
OK
2.
2.253 s
OK
3.
2.237 s
OK
4.
2.271 s
OK
1.
2.257 s
OK
2.
2.061 s
OK
1.
1.854 s
OK
1.
1.793 s
OK
1.
1.956 s
OK
2.
2.253 s
OK
3.
2.238 s
OK
expand all
Performance tests
1.
2.268 s
OK
1.
2.560 s
OK
2.
2.704 s
OK
1.
2.693 s
OK
1.
2.679 s
OK
2.
2.659 s
OK
3.
2.689 s
OK
1.
2.554 s
OK
2.
2.691 s
OK