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.

## No comments:

## Post a Comment