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