Consecutive numbers at distance less than or equal to 2, only two consecutives at distance 1. X96493
In this exercise you have to implement a function which receives a vector of integers satisfying the following property. Any pair of consecutive values in the vector are at a distance less than or equal to 2 from each other. Moreover, there is only one pair of consecutive values which are exactly at distance 1. For instance, the following sequence of values satisfies this property:
3 1 1 2 4 2 2 0
The function has to return the position (indexing from 0) of the first element of the consecutive pair which has distance 1. With the previous example as the input, the function would return 2.
This is the header:
// Pre: Let n be v.size(). Then, for each i in {0..n-2}, |v[i]-v[i+1]|<=2 holds.
// In addition, there is exactly one i in {0..n-2} satisfying |v[i]-v[i+1]|=1.
// Post: The function returns this particular i in {0..n-2} satisfying |v[i]-v[i+1]|=1.
int positionDistance1(const vector<int> &v);
Observation You only need to submit the required procedure; your main program will be ignored.
Observation
Evaluation out of 10 points:
- Slow solution: 5 points.
- Fast solution: 10 points.
A fast solution is one which is correct, of logarithmic cost and passing the test cases, both public and private. A slow solution is one which is not fast, but it is correct and passes the public test cases.
positionDistance1([-1, -1, 0, 0]) = 1 positionDistance1([5, 5, 7, 7, 9, 9, 11, 10, 8, 6, 6, 6]) = 6 positionDistance1([2, 0, 2, 4, 6, 6, 6, 6, 8, 7, 5, 3]) = 8 positionDistance1([-9, -9, -9, -10, -12, -14]) = 2 positionDistance1([10, 10, 12, 14, 15]) = 3 positionDistance1([9, 9, 11, 13, 11, 13, 15, 15, 15, 16, 14, 16, 14, 16, 18, 18]) = 8 positionDistance1([4, 2, 0, -2, -4, -5, -7, -5, -3, -5]) = 4 positionDistance1([-7, -9, -7, -5, -6]) = 3 positionDistance1([-2, -2, -4, -6, -4, -6, -6, -6, -6, -8, -10, -8, -7, -7, -5, -5]) = 11 positionDistance1([4, 6, 7, 5, 5, 7, 7, 9, 11]) = 1 positionDistance1([10, 10, 12, 12, 10, 8, 8, 9, 11, 9, 11, 9]) = 6 positionDistance1([0, 2, 0, -2, -1, -1, 1, 3, 5, 5, 3, 5, 7]) = 3 positionDistance1([-7, -9, -9, -7, -7, -6, -8, -6, -4, -4, -2, -4, -4, -2]) = 4 positionDistance1([-8, -6, -6, -4, -4, -4, -2, -2, -4, -4, -2, 0, -2, -4, -2, -2, -4, -5, -5]) = 16 positionDistance1([3, 5, 7, 6]) = 2 positionDistance1([6, 7, 7]) = 0 positionDistance1([7, 9, 10]) = 1 positionDistance1([5, 7, 7, 8, 8, 10, 12, 14, 14, 14, 14, 12, 10, 8, 6, 8, 6, 8]) = 2 positionDistance1([-2, 0, 2, 2, 4, 4, 2, 3, 5, 7, 7, 5, 7, 5]) = 6 positionDistance1([5, 3, 2, 4, 6]) = 1