Codility MinAvgTwoSlice

Given a vector sized 2 or more, find the index where starts the first subsequence of two or more elements with a minimal average value.

Like CountDiv, I don't get why this problem is in the Codility Prefix Sum section. To solve it we could create our sort-of partial sums vector, but this would just add space complexity without giving anything back.

I guess the most interesting point in this problem is about the size of candidate subsequences. Let's say that we have spotted a good subsequence of four elements in our vector. We would always find a way of splitting it and get the same or better result by one of its subsequences, think for instance to { 1, 1, 1, 1 } . We can't always do that when the elements are just three, and this is as an example: { -12, 0, -12 }.

So, that's it. We need to check for 2- and 3- sized subsequences.

Here are a few GoogleTest C++11 test cases:
TEST(MinAvgTwoSlice, Given)
{
    std::vector<int> input { 4, 2, 2, 5, 1, 5, 8 };
    ASSERT_EQ(1, solution(input));
}

TEST(MinAvgTwoSlice, Neg)
{
    std::vector<int> input { 4, 2, 2, 5, -100, 5, -100 };
    ASSERT_EQ(4, solution(input));
}

TEST(MinAvgTwoSlice, Last)
{
    std::vector<int> input { 100, 100, 1 };
    ASSERT_EQ(1, solution(input));
}
And this is my solution:
int solution(std::vector<int>& input)
{
    assert(input.size() > 1); // 1

    int index = 0;
    double minimal = std::numeric_limits<double>::max();
    for(unsigned i = 0; i < input.size() - 2; ++i) // 2
    {
        double candidate = (input[i] + input[i+1]) / 2.0; // 3
        if(candidate < minimal)
        {
            index = i;
            minimal = candidate;
        }

        candidate = (input[i] + input[i+1] + input[i+2]) / 3.0; // 4
        if(candidate < minimal)
        {
            index = i;
            minimal = candidate;
        }
    }

    double candidate = (input.back() + *(input.rbegin() + 1)) / 2.0; // 5
    if(candidate < minimal)
        return input.size() - 2;

    return index;
}
1. Problem prerequisite.
2. Looping an all the elements but the last couple.
3. Check the current couple.
4. Check the current triplet.
5. Last couple.

No comments:

Post a Comment