Codility Triangle

Given a vector of integer, detect if there is at least a triplet of elements that could represent the length of edges in a triangle.

You could find this "painless" problem in the Sorting section, practicing area, on the codility web site.

I have already solved it in a previous post, when codility referred to a C++98 compiler. Here I refactor the solution for the current C++11 codility programming environment. Please look at the previous post for more chatting on it.

We know that in a triangle, the sum of any two edges should be less that the third one, this lead to the condition we have to verify. Our function would get in input a STL vector of int, and return 1 for success and 0 for failure.

A couple of test case for this problem, C++11 for GoogleTest:

TEST(Triangle, Given1)
{
    std::vector<int> input { 10, 2, 5, 1, 8, 20 };
    ASSERT_EQ(1, solution(input));
}

TEST(Triangle, Given2)
{
    std::vector<int> input { 10, 50, 5, 1 };
    ASSERT_EQ(0, solution(input));
}

I have implemented my solution in this way:

int solution(std::vector<int>& input)
{
    if(input.size() < 3) // 1
    {
        return 0;
    }

    std::sort(input.begin(), input.end()); // 2

    for(unsigned i = 2; i < input.size(); ++i) // 3
    {
        if(input[i] < 0) // 4
        {
            i += 2;
            continue;
        }

        if(static_cast<unsigned>(input[i - 2] + input[i - 1]) > static_cast<unsigned>(input[i])) // 5
        {
            return 1;
        }
    }

    return 0;
}

1. Paranoid check, not required by codility.
2. Instead of checking all the possible triplets, that would generate a cubic time complexity solution, we can sort the input data before checking them.
3. Check all the possible triplets. The i-th one represent the third element in the current triplet.
4. We should expect also negative elements in input, still they make no sense for our problem. If the i-th element is negative, we can safely discard the current triplet and the next two ones (that would include this negative value).
5. We are considering three positive sorted elements. It is enough to ensure that the third one is bigger than the sum of the previous two ones to answer to the original question. I need to cast the values to unsigned to avoid any possible overflow problem.