# How to solve this algorithm challenge with prefix sums?

Challenge is over here: MinAvgTwoSlice coding task - Learn to Code - Codility.
Click “START” and later you can choose any language to solve it.

It’s meant to teach you about prefix sums, but even though I understand what prefix sums are, I couldn’t figure out how to apply the technique here. Could anyone please help?

They provided reading material on prefix sums here: 3-PrefixSums.pdf (codility.com)

PS I did manage to solve the challenge the way below (you don’t need to read it), but it doesn’t use prefix sums and it took me ages to come up with it. I can’t help but thinking if I had a better understanding about prefix sums, I would have spent much less time on it.

``````function avgX(prevAvg, num, prevCount = 1) {
return (prevAvg * prevCount + num) / (prevCount + 1)
}

function solution(A) {
let answer = 0,
minAvg = (A[0]+A[1])/2,
avg = minAvg,
start = 0;
count = 2;
let i = 1;

while(i < A.length - 1) {
if(A[i+1] <= avg) {
avg = avgX(avg, A[i+1], count);
count++;
} else if(avgX(A[i], A[i+1]) === avg) {
if(avg < minAvg) {
minAvg = avg;
}
start = i;
count = 2;
}
if(avgX(A[i], A[i+1]) < avg) {
avg = avgX(A[i], A[i+1]);
start = i;
count = 2;
} else if(avgX(A[i], A[i+1]) > avg) {
if(avg < minAvg) {
minAvg = avg;
}
avg = avgX(A[i], A[i+1]);
start = i;
count = 2;
}
i++;
}
if(avg < minAvg) answer = start;
}
``````

Hi!

Here’s my solution using prefix sum. I do need to find a more efficient way though - low performance score, medium_random was the only performance test that did not time out…

``````
def solution(A):
# write your code in Python 3.6
minAvg = 10000
result = 0

N = len(A)
pSum = [0] * (N + 1)
for i in range(1, N + 1):
pSum[i] = pSum[i - 1] + A[i - 1]

for j in range(i-1):
thisAvg = (pSum[i] - pSum[j])/(i-j)
if minAvg > thisAvg:
minAvg = thisAvg
result = j

return result
``````

Please do give me feedback! Amateur here!

Also, thank you for posting this - just discovered Codility through it and it looks fun and challenging!

Here is the O(N) solution to this problem using prefix sums. By storing the prefix sum and the its start/end index I can pull up its average any time. Storing the average itself can prove difficult when you want to add to it.

I have commented throughout the solution and I believe the basic logic is the same as yours.

``````function solution(A) {
let run=A[0]+A[1];
let start=0;
let end=1;

//default
let minAvg=run/2;
let ans=0;

//to evaluate in each for loop
let runAvg;
let curr;

//start on i=1 due to starting case being i=0 to i=1 already
for (let i = 1; i < A.length-1; i++) {
//current best avg
runAvg=run/(end-start+1);
//avg of curr slice of two
curr=(A[i]+A[i+1]);
//case curr running avg worse
if (runAvg>curr/2) {
//case adding new element makes running avg better
if ((run+A[i+1])/(end-start+2)<curr/2) {
run+=A[i+1];
end++;
}
else {
//start new with curr slice of two
run=curr;
start=i;
end=i+1;
}

}
//case curr running avg better
else if (runAvg<curr/2) {
//compare with best, keep minimum of two
if (runAvg<minAvg) {
minAvg=runAvg;
ans=start;
}
//start new with curr slice of two
run=curr;
start=i;
end=i+1;
}
//case curr running avg the same
else {
//add to curr for possibility of smaller slice in future
run+=A[i+1];
end++;
}
}
//edge case of end of array being best
if (run/(end-start+1)<minAvg)
return start;
return ans;
}
``````

to @parvathy0, you have a great start, good job. This is the naive and straight forward solution and is definitely correct logically. However it is O(N^2) in terms of time complexity, and you can add some clever stuff in there to eliminate your inner for loop entirely.

2 Likes

Thanks!

So the prefix sums part is where you did `run+=A[i+1]`?

1 Like

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.