Tasks Details
medium
Find the minimal average of any slice containing at least two elements.
Task Score
60%
Correctness
80%
Performance
40%
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:
def solution(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–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 8 minutes
Notes
not defined yet
Task timeline
Code: 02:09:47 UTC,
java,
autosave
Code: 02:10:11 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,3,6)]
for q in range(2,len(A)):
num_qp = d[q-1][2] // d[q-1][1]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
min_p = 0
min_q = 1
for q in range(1,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
Code: 02:10:33 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,3,6)]
for q in range(2,len(A)):
num_qp = d[q-1][2] // d[q-1][1]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
min_p = 0
min_q = 1
for q in range(1,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
Code: 02:11:04 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,6)]
for q in range(2,len(A)):
num_qp = d[q-1][2] // d[q-1][1]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
min_p = 0
min_q = 1
for q in range(1,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
Code: 02:11:08 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = d[q-1][2] // d[q-1][1]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
min_p = 0
min_q = 1
for q in range(1,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
User test case 1:
[-18, 65, -11, 73, -22, 90, 21, 10, 47, 87]
Analysis
Code: 02:11:26 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = d[q-1][2] // d[q-1][1]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
min_p = 0
min_q = 1
for q in range(1,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
User test case 1:
[-18, 65, -11, 73, -22, 90, 21, 10, 47, 87]
User test case 2:
[5, 6, 3, 4, 9]
Analysis
Code: 02:11:59 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = d[q-1][2] // d[q-1][1]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
min_p = 0
min_q = 1
for q in range(1,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
Code: 02:12:10 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = d[q-1][2] // d[q-1][1]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
min_p = 0
min_q = 1
for q in range(1,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
Code: 02:12:22 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = i - d[q-1][]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
min_p = 0
min_q = 1
for q in range(1,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
Code: 02:12:30 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = i - d[q-1][0]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
min_p = 0
min_q = 1
for q in range(1,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
User test case 1:
[-18, 65, -11, 73, -22, 90, 21, 10, 47, 87]
User test case 2:
[5, 6, 3, 4, 9]
Analysis
expand all
Example tests
1.
0.036 s
WRONG ANSWER,
got 0 expected 1
Code: 02:12:44 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = i - d[q-1][0]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
min_p = 0
min_q = 1
for q in range(2,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
Code: 02:12:58 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = i - d[q-1][0]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
print(d)
min_p = 0
min_q = 1
for q in range(2,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
User test case 1:
[-18, 65, -11, 73, -22, 90, 21, 10, 47, 87]
User test case 2:
[5, 6, 3, 4, 9]
Analysis
expand all
Example tests
1.
0.036 s
WRONG ANSWER,
got 0 expected 1
stdout:
[(0, 0, 0), (0, 3, 6), (0, 0.8888888888888888, 8), (1, 1.4444444444444444, 13), (2, 1.75, 14), (3, 2.7142857142857144, 19), (4, 4.5, 27)]
expand all
User tests
1.
0.036 s
OK
function result: 0
function result: 0
stdout:
[(0, 0, 0), (0, 23, 47), (0, 0.4090909090909091, 36), (1, 1.2386363636363635, 109), (2, 1.0, 87), (3, 2.058139534883721, 177), (4, 2.3294117647058825, 198), (5, 2.4761904761904763, 208), (6, 3.072289156626506, 255), (7, 4.170731707317073, 342)]
1.
0.036 s
OK
function result: 0
function result: 0
stdout:
[(0, 0, 0), (0, 5, 11), (0, 1.4, 14), (1, 1.8, 18), (2, 3.0, 27)]
Code: 02:13:40 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = i - d[q-1][0]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
print(d)
min_p = 0
min_q = 1
for q in range(2,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
Code: 02:13:51 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = i - d[q-1][0]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /num_qp) < a_a/2 :
d.append((q-2, d_a /num_qp, d_a))
else:
d.append((q-1, a_a/2, a_a))
print(d)
min_p = 0
min_q = 1
for q in range(2,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
User test case 1:
[-18, 65, -11, 73, -22, 90, 21, 10, 47, 87]
User test case 2:
[5, 6, 3, 4, 9]
Analysis
expand all
Example tests
1.
0.040 s
WRONG ANSWER,
got 0 expected 1
stdout:
[(0, 0, 0), (0, 3, 6), (0, 1.0, 8), (1, 1.625, 13), (2, 2.0, 14), (4, 3.0, 6), (4, 3.5, 14)]
expand all
User tests
1.
0.040 s
OK
function result: 0
function result: 0
stdout:
[(0, 0, 0), (0, 23, 47), (0, 0.41379310344827586, 36), (1, 1.2528735632183907, 109), (2, 1.0116279069767442, 87), (3, 2.0823529411764707, 177), (4, 2.357142857142857, 198), (5, 2.5060240963855422, 208), (6, 3.1097560975609757, 255), (7, 4.222222222222222, 342)]
1.
0.040 s
OK
function result: 0
function result: 0
stdout:
[(0, 0, 0), (0, 5, 11), (0, 1.5555555555555556, 14), (1, 2.0, 18), (2, 3.375, 27)]
Code: 02:15:34 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = i - d[q-1][0]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /num_qp) < a_a/2 :
d.append((q-2, d_a /num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
print(d)
min_p = 0
min_q = 1
for q in range(2,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
Code: 02:15:38 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = i - d[q-1][0]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
print(d)
min_p = 0
min_q = 1
for q in range(2,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
User test case 1:
[-18, 65, -11, 73, -22, 90, 21, 10, 47, 87]
User test case 2:
[5, 6, 3, 4, 9]
Analysis
expand all
Example tests
1.
0.036 s
WRONG ANSWER,
got 0 expected 1
stdout:
[(0, 0, 0), (0, 3, 6), (0, 0.8888888888888888, 8), (1, 1.4444444444444444, 13), (2, 1.75, 14), (3, 2.7142857142857144, 19), (4, 4.5, 27)]
expand all
User tests
1.
0.036 s
OK
function result: 0
function result: 0
stdout:
[(0, 0, 0), (0, 23, 47), (0, 0.4090909090909091, 36), (1, 1.2386363636363635, 109), (2, 1.0, 87), (3, 2.058139534883721, 177), (4, 2.3294117647058825, 198), (5, 2.4761904761904763, 208), (6, 3.072289156626506, 255), (7, 4.170731707317073, 342)]
1.
0.036 s
OK
function result: 0
function result: 0
stdout:
[(0, 0, 0), (0, 5, 11), (0, 1.4, 14), (1, 1.8, 18), (2, 3.0, 27)]
Code: 02:16:14 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = q - d[q-1][0]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
print(d)
min_p = 0
min_q = 1
for q in range(2,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
Code: 02:16:17 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = q - d[q-1][0]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
print(d)
min_p = 0
min_q = 1
for q in range(2,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
User test case 1:
[-18, 65, -11, 73, -22, 90, 21, 10, 47, 87]
User test case 2:
[5, 6, 3, 4, 9]
Analysis
expand all
Example tests
1.
0.052 s
OK
stdout:
[(0, 0, 0), (0, 3, 6), (1, 2.0, 4), (1, 3.0, 9), (2, 2.5, 10), (4, 3.0, 6), (4, 4.666666666666667, 14)]
expand all
User tests
1.
0.036 s
OK
function result: 0
function result: 0
stdout:
[(0, 0, 0), (0, 23, 47), (0, 12.0, 36), (1, 27.25, 109), (2, 21.75, 87), (4, 34.0, 68), (4, 29.666666666666668, 89), (6, 15.5, 31), (6, 26.0, 78), (7, 41.25, 165)]
1.
0.036 s
OK
function result: 2
function result: 2
stdout:
[(0, 0, 0), (0, 5, 11), (1, 4.5, 9), (2, 3.5, 7), (2, 5.333333333333333, 16)]
Code: 02:16:36 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = q - d[q-1][0]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
#print(d)
min_p = 0
min_q = 1
for q in range(2,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
Code: 02:16:40 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = q - d[q-1][0]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
#print(d)
min_p = 0
min_q = 1
for q in range(2,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
User test case 1:
[-18, 65, -11, 73, -22, 90, 21, 10, 47, 87]
User test case 2:
[5, 6, 3, 4, 9]
Analysis
Code: 02:16:44 UTC,
py,
final,
score:
60
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
# write your code in Python 3.6
s = [0]
tmp=0
for i in A:
tmp+=i
s.append(tmp)
d = [(0,0,0),(0,(A[0]+A[1])//2,A[0]+A[1])]
for q in range(2,len(A)):
num_qp = q - d[q-1][0]
d_a = d[q-1][2]+A[q]
a_a = A[q-1]+A[q]
if (d_a /(num_qp+1)) < a_a/2 :
d.append((q-2, d_a /(num_qp+1), d_a))
else:
d.append((q-1, a_a/2, a_a))
#print(d)
min_p = 0
min_q = 1
for q in range(2,len(d)):
if d[q][1] < d[min_q][1]:
min_q = q
min_p = d[q][0]
return min_p
Analysis summary
The following issues have been detected: wrong answers.
Analysis
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
1.
0.036 s
WRONG ANSWER,
got 61 expected 17
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
expand all
Performance tests
1.
0.036 s
WRONG ANSWER,
got 591 expected 90
1.
0.248 s
WRONG ANSWER,
got 57737 expected 0
2.
0.196 s
WRONG ANSWER,
got 0 expected 40002
1.
0.252 s
WRONG ANSWER,
got 95508 expected 46034
1.
0.248 s
OK
2.
0.256 s
OK
3.
0.260 s
OK
1.
0.248 s
OK
2.
0.184 s
OK