Codility MissingInteger

Given a not empty integer vector, returns the minimal positive number not seen in input. You could find this problem in the Codility test Counting Elements section. It is marked as "respectable", even though it doesn't seem more complicated than an average "painless" one.

To clarify what we are looking for, here is a bunch of C++11 GTest test cases:
TEST(MissingInteger, One) // 1
{
    std::vector<int> input { 1 };
    ASSERT_EQ(2, solution(input));
}

TEST(MissingInteger, Neg) // 2
{
    std::vector<int> input { -3 };
    ASSERT_EQ(1, solution(input));
}

TEST(MissingInteger, Given) // 3
{
    std::vector<int> input { 1, 3, 6, 4, 1, 2 };
    ASSERT_EQ(5, solution(input));
}

TEST(MissingInteger, Sequence) // 4
{
    std::vector<int> input { 1, 2, 3, 4, 5, 6, 7 };
    ASSERT_EQ(8, solution(input));
}
1. Only one integer in input.
2. We could have negative integer in input.
3. Example provided by Codility.
4. Natural sequence.

An intuitive solution would be checking all the positive numbers in [1..n], where n is the vector size, and returning as soon as we find a missing value. But think to test 4. It is the worst case scenario. I'll check all the element, to see that no one of them is missing, and so I would return n+1, with a n-squared complexity.

To achieve a time-linear solution, we should use some extra memory. We'll scan the input vector just once, setting a flag for each found positive number. Then I'll search for the first unset flag, and that's it:
int solution(std::vector<int>& input)
{
    std::vector<bool> flags(input.size()); // 1

    std::for_each(input.begin(), input.end(), [&flags](int cur){ // 2
        if(cur > 0 && cur <= static_cast<int>(flags.size())) // 3
            flags[cur - 1] = true;
    });

    return std::find(flags.begin(), flags.end(), false) - flags.begin() + 1; // 4
}
1. A flag for each expected (in the worst case) positive integer in input.
2. Loop on all the input data
3. If I the current value is positive and in the expected range, convert it to a valid index for the flags buffer, and mark that element as seen.
4. Find the index of the first missing element (remember that the STL find() function return the end() iterator in case it doesn't find anything, and this behavior is just what we want here), convert it back to the related value an return it.

Go to the full post

Codility PermCheck

We have in input an integer vector, and we want to check if it is a permutation of the natural sequence [1..n], where n is the vector size.
You could find this problem in the Codility test Counting Elements section.

I have already written a post about it, where I provide some test cases and a few different C++ solutions. Some time has passed, I am solving them from scratch, this time using C++11, that in the meantime has become supported by Codility. Please have a look at it for more details.

Here is my current solution:
int solution(std::vector<int>& input)
{
    std::vector<bool> flags(input.size()); // 1

    for(auto it = input.begin(); it != input.end(); ++it) // 2
    {
        unsigned index = *it - 1; // 3
        if(index >= input.size() || flags[index]) // 4
            return 0;
        flags[index] = true;
    }

    return 1; // 5
//    return std::find(flags.begin(), flags.end(), false) == flags.end();
}
1. The idea is to use a buffer where I keep track of all the expected elements. Initially no one has been seen, once I find a number I flag it.
2. Loop on all the elements.
3. Convert the current value in its associated zero-based vector index.
4. If the index is outside the expected range, or if the flag has already been set for this value, the sequence is not a permutation. Return the required failure value.
5. If I get here, the sequence has been checked and found OK, return the success value. Actually, also this time I didn't notice that, and I originally wrote the next line, now commented, to explicitly check that any number is found. This is useless, since I have already checked in (4) all possible cases.

Go to the full post

Codility FrogRiverOne

This problem is described in the Codility web site, Counting Elements section.
We are asked to check if the integer vector passed in input contains all the values in the natural sequence from 1 up to a passed number.

I have already given a couple of C++ solutions (a Big-Oh-Squared and a linear one) in a previous post. Here I give the C++ solution that jumped now to my mind, and it sort of look cleaner to me.

First of all, a couple of test cases (based on the GTest framework) that should clarify the problem:
TEST(FrogRiverOne, Given)
{
    std::vector<int> input { 1, 3, 1, 4, 2, 3, 5, 4 }; // 1
    ASSERT_EQ(6, solution(5, input));
}

TEST(FrogRiverOne, Cannot)
{
    std::vector<int> input { 1, 3, 1, 4, 2, 3, 5, 4 }; // 2
    ASSERT_EQ(-1, solution(6, input));
}
1. The Codility given test case. Given this vector, we want to get the index of the first element so that any value in [1 .. 5] is available. That means 6, given that 1 is at position 0 (and 2), 2 at 4, 3 at 1 (and 5), 4 at 3, and finally 5 at 6.
2. A negative case, 6 is not in the passed vector, so we should return -1.

Here is my latest solution:
int solution(int x, std::vector<int>& input)
{
    assert(x > 0); // 1
    assert(!input.empty());

    std::vector<bool> flags(x-1); // 2
    for(unsigned i = 0; i < input.size(); ++i) // 3
    {
        unsigned index = input[i] - 1; // 4
        if(!flags[index]) // 5
        {
            flags[index] = true;
            if(--x == 0)
                return i; // 6
        }
    }

    return -1; // 7
}
1. Enforce the most sensitive problem requisite. This is not requested by Codility, that ensures only "clean" input data are provided.
2. When I see a number in [1..x] I mark it as found. Here I store the flags for this purpose.
3. Loop on all the vector input elements.
4. Convert the current input value so that I can use it as an index for the flags vector. Production code should ensure that index is not outside the range of valid values.
5. If I see this value for the first time, I mark it as found, and I decrease the number of missing value that I am looking for.
6. When I have found all the expected elements, I return the current index in the input vector.
7. Otherwise not-found is returned.

Go to the full post

Codility FrogJmp

You could find the full description of this problem, and check your solution in (possibly) your favorite programming language, on the Codility web site, Time Complexity section. To simply put it, we have to calculate a distance, and determine how many segments of a given size we need to cover that distance.

It is marked as "painless", even if "embarrassingly simple" would probably be a better description. Still, even in this case a mistake could be lurking somewhere, ready to catch us off guard. Here the issue could be that we need to consider two cases, and one of them could be overseen. Here is a couple of test cases (C++, GoogleTest) that clarifies the matter:
TEST(FrogJmp, Given) // 1
{
    ASSERT_EQ(3, solution(10, 85, 30));
}

TEST(FrogJmp, Precise)
{
    ASSERT_EQ(4, solution(10, 90, 20));
}
1. A frog starts its trip on 10, wants to reach 85, and its jump is sized 30. Obviously it needs three steps to get it.
2. A weaker frog on a longer path. In four steps it gets exactly on its end point.

Here is how implemented my solution:
int solution(int x, int y, int d)
{
    assert(x < y); // 1
    assert(d > 0);

    int distance = y - x; // 2
    int steps = distance / d; // 3
    if(distance % d != 0) // 4
        ++steps;
    return steps;
}
1. Assuming no tricky input. The frog starts on the left and goes to the right.
2. This is the distance it has to travel.
3. The solution is just a matter of dividing the distance for the step size ...
4. ... plus one, in case our frog is not lucky enough to drop right on its path end.

Go to the full post

Codility Tape Equilibrium

The Codility Tape Equilibrium problem is marked as "painless" in their Time Complexity section. Basically, we have a vector in input, containing at least two items, and we want to split it in a way that minimize the difference between the two sections. Our function should return such a minimal value.

A few test cases would make clearer what we are looking for:

TEST(TapeEquilibrium, Given) // 1
{
    std::vector<int> input { 3, 1, 2, 4, 3 };
    ASSERT_EQ(1, solution(input));
}

TEST(TapeEquilibrium, Couple)
{
    std::vector<int> input { 3, 3 };
    ASSERT_EQ(0, solution(input));
}

TEST(TapeEquilibrium, Couple2)
{
    std::vector<int> input { 1000, -1000 };
    ASSERT_EQ(2000, solution(input));
}

TEST(TapeEquilibrium, HundredK) // 2
{
    std::vector<int> input(100000, 1000);

    EXPECT_EQ(0, solution(input));
}

TEST(TapeEquilibrium, HundredKMinusOne)
{
    std::vector<int> input(99999, 1000);

    EXPECT_EQ(1000, solution(input));
}
1. This is the test case provided by Codility. It should be easy to see how we minimize the difference by splitting the input in {3, 1, 2} and {4, 3}. The expected output of our function is one.
2. Hundred thousand items, each of them set to one thousand. Lot of work for our function, but it is easy to see how the solution should be zero.

If you wonder, these are C++11 tests written for the GoogleTest xUnit framework. If you are using an older C++ compiler, you could have a look to a previous version of this post, that also shows a bad, O(N**2), alternative solution.

My linear time solution starts creating two partial sums, left and right, where initially the left one contains only the leftmost element, and the right one all the others. Then, I would remove one element at the time from the right one and add it to the left one. Each time I should repeat the check to see if I find a better solution.

Here is how I implemented it:
int solution(std::vector<int>& input) // 1
{
    assert(input.size() > 1); // 2

    int left = input.front(); // 3
    int right = std::accumulate(input.begin() + 1, input.end(), 0); // 4
    int result = std::abs(left - right); // 5

    std::for_each(input.begin() + 1, input.end() - 1, [&](int cur){ // 6
        left += cur;
        right -= cur;
        int tentative = std::abs(left - right);
        if(tentative < result) // 7
            result = tentative;
    });

    return result;
}
1. Actually, the input vector could and should be a const reference. Codility requirements are sometimes a bit sloppy.
2. Not required by the problem, however I felt bad to assume such a requisite without enforcing it in the code is some way.
3. Initializing the left sum is easy.
4. The right sum requires a bit more work. To keep the code more readable I used the handy STL accumulate function.
5. Initialize the function result. Notice that we are interested in the difference about left and right without caring about its sign.
6. A nice lambda function in a for_each loop keeps the code compact and, hopefully, readable. I am starting to loop from the second element, and I would end one before the end, since no section should be empty.
7. This is a better candidate, save it.

Go to the full post