Pages

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.

No comments:

Post a Comment