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) {
                answer = start;
                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) {
                answer = start;
                minAvg = avg;
            }
            avg = avgX(A[i], A[i+1]);
            start = i;
            count = 2;
        }
        i++;
    }
    if(avg < minAvg) answer = start;
    return answer;
}

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! :slight_smile:

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) {
    //start with index 0 and 1
    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.