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.