Test results - Codility

Tasks Details

medium

1. MinAvgTwoSlice

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] = 8

contains 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:

function 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] = 8

the 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].

Solution

Programming language used JavaScript

Time spent on task 4 minutes

Notes

not defined yet

Code: 06:08:48 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
    }
}

Code: 06:08:59 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    /* Consider a slice of size 4. You can always break it down into two slices of size 2. One of two cases may happen. First, the averages of the two slices are the same, in which case, you could just use the first average. Second, the averages are different, in which case, your original slice cannot be the min-average slice. So the slice of size 4 is either duplicated with a shorter slice, or not the min. You cannot make this argument with a slice of size 3.*/

    const N = A.length;

    let lowestIndex = 0;
    let lowestAvg = Number.MAX_SAFE_INTEGER;
    let last = undefined;
    let lastButOne = undefined;

    for (let i = 0; i < N; i ++) {
        if (last !== undefined) {
            const avg = (last + A[i]) / 2;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 1;
            }
        }

        if (lastButOne !== undefined) {
            const avg = (lastButOne + last + A[i]) / 3;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 2;
            }
        }

        last = A[i];
        lastButOne = last;
    }

    return lowestIndex;
}

Code: 06:09:18 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    /* Consider a slice of size 4. You can always break it down into two slices of size 2. One of two cases may happen. First, the averages of the two slices are the same, in which case, you could just use the first average. Second, the averages are different, in which case, your original slice cannot be the min-average slice. So the slice of size 4 is either duplicated with a shorter slice, or not the min. You cannot make this argument with a slice of size 3.*/

    const N = A.length;

    let lowestIndex = 0;
    let lowestAvg = Number.MAX_SAFE_INTEGER;
    let last = undefined;
    let lastButOne = undefined;

    for (let i = 0; i < N; i++) {
        if (last !== undefined) {
            const avg = (last + A[i]) / 2;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 1;
            }
        }

        if (lastButOne !== undefined) {
            const avg = (lastButOne + last + A[i]) / 3;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 2;
            }
        }

        last = A[i];
        lastButOne = last;
    }

    return lowestIndex;
}

Code: 06:09:49 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    /* Consider a slice of size 4. You can always break it down into two slices of size 2. One of two cases may happen. First, the averages of the two slices are the same, in which case, you could just use the first average. Second, the averages are different, in which case, your original slice cannot be the min-average slice. So the slice of size 4 is either duplicated with a shorter slice, or not the min. You cannot make this argument with a slice of size 3.*/

    const N = A.length;

    let lowestIndex = 0;
    let lowestAvg = Number.MAX_SAFE_INTEGER;
    let last = undefined;
    let lastButOne = undefined;

    for (let i = 0; i < N; i++) {
        if (last !== undefined) {
            const avg = (last + A[i]) / 2;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 1;
            }
        }

        last = A[i];
        lastButOne = last;
    }

    return lowestIndex;
}

Code: 06:10:00 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    /* Consider a slice of size 4. You can always break it down into two slices of size 2. One of two cases may happen. First, the averages of the two slices are the same, in which case, you could just use the first average. Second, the averages are different, in which case, your original slice cannot be the min-average slice. So the slice of size 4 is either duplicated with a shorter slice, or not the min. You cannot make this argument with a slice of size 3.*/

    const N = A.length;

    let lowestIndex = 0;
    let lowestAvg = Number.MAX_SAFE_INTEGER;
    let last = undefined;
    let lastButOne = undefined;

    for (let i = 0; i < N; i++) {
        if (lastButOne !== undefined) {
            const avg = (lastButOne + last + A[i]) / 3;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 2;
            }
        }

        if (last !== undefined) {
            const avg = (last + A[i]) / 2;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 1;
            }
        }

        last = A[i];
        lastButOne = last;
    }

    return lowestIndex;
}

Code: 06:10:28 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    /* Consider a slice of size 4. You can always break it down into two slices of size 2. One of two cases may happen. First, the averages of the two slices are the same, in which case, you could just use the first average. Second, the averages are different, in which case, your original slice cannot be the min-average slice. So the slice of size 4 is either duplicated with a shorter slice, or not the min. You cannot make this argument with a slice of size 3.*/

    const N = A.length;

    let lowestIndex = 0;
    let lowestAvg = Number.MAX_SAFE_INTEGER;
    let last = undefined;
    let lastButOne = undefined;

    for (let i = 0; i < N; i++) {
        if (lastButOne !== undefined) {
            const avg = (lastButOne + last + A[i]) / 3;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 2;
            }
        }

        if (last !== undefined) {
            const avg = (last + A[i]) / 2;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 1;
            }
        }

        last = A[i];
        lastButOne = last;
    }

    return lowestIndex;
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 0 expected 1

0.072 s

WRONG ANSWER, got 0 expected 1

Code: 06:10:35 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    /* Consider a slice of size 4. You can always break it down into two slices of size 2. One of two cases may happen. First, the averages of the two slices are the same, in which case, you could just use the first average. Second, the averages are different, in which case, your original slice cannot be the min-average slice. So the slice of size 4 is either duplicated with a shorter slice, or not the min. You cannot make this argument with a slice of size 3.*/

    const N = A.length;

    let lowestIndex = 0;
    let lowestAvg = Number.MAX_SAFE_INTEGER;
    let last = undefined;
    let lastButOne = undefined;

    for (let i = 0; i < N; i++) {
        if (lastButOne !== undefined) {
            const avg = (lastButOne + last + A[i]) / 3;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 2;
            }
        }

        if (last !== undefined) {
            const avg = (last + A[i]) / 2;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 1;
            }
        }

        last = A[i];
        lastButOne = last;
    }

    return lowestIndex;
}

Analysis

expand all Example tests

▶

example
example test

✘

WRONG ANSWER
got 0 expected 1

0.072 s

WRONG ANSWER, got 0 expected 1

Code: 06:11:45 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    /* Consider a slice of size 4. You can always break it down into two slices of size 2. One of two cases may happen. First, the averages of the two slices are the same, in which case, you could just use the first average. Second, the averages are different, in which case, your original slice cannot be the min-average slice. So the slice of size 4 is either duplicated with a shorter slice, or not the min. You cannot make this argument with a slice of size 3.*/

    const N = A.length;

    let lowestIndex = 0;
    let lowestAvg = Number.MAX_SAFE_INTEGER;
    let last = undefined;
    let lastButOne = undefined;

    for (let i = 0; i < N; i++) {
        if (lastButOne !== undefined) {
            const avg = (lastButOne + last + A[i]) / 3;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 2;
            }
        }

        if (last !== undefined) {
            const avg = (last + A[i]) / 2;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 1;
            }
        }


        lastButOne = last;
    }

    return lowestIndex;
}

Code: 06:11:50 UTC, js, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    /* Consider a slice of size 4. You can always break it down into two slices of size 2. One of two cases may happen. First, the averages of the two slices are the same, in which case, you could just use the first average. Second, the averages are different, in which case, your original slice cannot be the min-average slice. So the slice of size 4 is either duplicated with a shorter slice, or not the min. You cannot make this argument with a slice of size 3.*/

    const N = A.length;

    let lowestIndex = 0;
    let lowestAvg = Number.MAX_SAFE_INTEGER;
    let last = undefined;
    let lastButOne = undefined;

    for (let i = 0; i < N; i++) {
        if (lastButOne !== undefined) {
            const avg = (lastButOne + last + A[i]) / 3;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 2;
            }
        }

        if (last !== undefined) {
            const avg = (last + A[i]) / 2;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 1;
            }
        }

        lastButOne = last;
        last = A[i];
    }

    return lowestIndex;
}

Analysis

expand all Example tests

▶

example
example test

✔

0.120 s

Code: 06:12:02 UTC, js, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    /* Consider a slice of size 4. You can always break it down into two slices of size 2. One of two cases may happen. First, the averages of the two slices are the same, in which case, you could just use the first average. Second, the averages are different, in which case, your original slice cannot be the min-average slice. So the slice of size 4 is either duplicated with a shorter slice, or not the min. You cannot make this argument with a slice of size 3.*/

    const N = A.length;

    let lowestIndex = 0;
    let lowestAvg = Number.MAX_SAFE_INTEGER;
    let last = undefined;
    let lastButOne = undefined;

    for (let i = 0; i < N; i++) {
        if (last !== undefined) {
            const avg = (last + A[i]) / 2;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 1;
            }
        }

        if (lastButOne !== undefined) {
            const avg = (lastButOne + last + A[i]) / 3;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 2;
            }
        }

        lastButOne = last;
        last = A[i];
    }

    return lowestIndex;
}

Analysis

expand all Example tests

▶

example
example test

✔

0.072 s

Code: 06:12:05 UTC, js, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    /* Consider a slice of size 4. You can always break it down into two slices of size 2. One of two cases may happen. First, the averages of the two slices are the same, in which case, you could just use the first average. Second, the averages are different, in which case, your original slice cannot be the min-average slice. So the slice of size 4 is either duplicated with a shorter slice, or not the min. You cannot make this argument with a slice of size 3.*/

    const N = A.length;

    let lowestIndex = 0;
    let lowestAvg = Number.MAX_SAFE_INTEGER;
    let last = undefined;
    let lastButOne = undefined;

    for (let i = 0; i < N; i++) {
        if (last !== undefined) {
            const avg = (last + A[i]) / 2;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 1;
            }
        }

        if (lastButOne !== undefined) {
            const avg = (lastButOne + last + A[i]) / 3;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 2;
            }
        }

        lastButOne = last;
        last = A[i];
    }

    return lowestIndex;
}

Analysis

expand all Example tests

▶

example
example test

✔

0.072 s

Code: 06:12:08 UTC, js, final, score: 100

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    /* Consider a slice of size 4. You can always break it down into two slices of size 2. One of two cases may happen. First, the averages of the two slices are the same, in which case, you could just use the first average. Second, the averages are different, in which case, your original slice cannot be the min-average slice. So the slice of size 4 is either duplicated with a shorter slice, or not the min. You cannot make this argument with a slice of size 3.*/

    const N = A.length;

    let lowestIndex = 0;
    let lowestAvg = Number.MAX_SAFE_INTEGER;
    let last = undefined;
    let lastButOne = undefined;

    for (let i = 0; i < N; i++) {
        if (last !== undefined) {
            const avg = (last + A[i]) / 2;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 1;
            }
        }

        if (lastButOne !== undefined) {
            const avg = (lastButOne + last + A[i]) / 3;

            if (avg < lowestAvg) {
                lowestAvg = avg;
                lowestIndex = i - 2;
            }
        }

        lastButOne = last;
        last = A[i];
    }

    return lowestIndex;
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

expand all Example tests

▶

example
example test

✔

0.072 s

expand all Correctness tests

▶

double_quadruple
two or four elements

✔

0.072 s

0.068 s

▶

simple1
simple test, the best slice has length 3

✔

0.072 s

▶

simple2
simple test, the best slice has length 3

✔

0.072 s

▶

small_random
random, length = 100

✔

0.072 s

▶

medium_range
increasing, decreasing (legth = ~100) and small functional

✔

0.072 s

expand all Performance tests

▶

medium_random
random, N = ~700

✔

0.072 s

▶

large_ones
numbers from -1 to 1, N = ~100,000

✔

0.104 s

0.100 s

▶

large_random
random, N = ~100,000

✔

0.128 s

▶

extreme_values
all maximal values, N = ~100,000

✔

0.112 s

▶

large_sequence
many seqeneces, N = ~100,000

✔

0.100 s