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