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.
