Search for distance d in vector with strictly increasing consecutive distances X42592
Implement a function that receives a natural d and a vector v with two or more elements and which satisfies the following condition: the sequence of distances between each pair of consecutive elements in v is strictly increasing, i.e. |v[0]−v[1]| < |v[1]−v[2]| < |v[2]−v[3]| < ⋯. For instance, the following sequence satisfies this condition:
3 2 4 8 0 -10 -22 -8 7
Note that the distance between the first and second element is 1, the distance between the second and third is 2, between the third and fourth is 4, between the fourth and fifth is 8, between the fifth and sixth is 10, between the sixth and seventh is 12, between the seventh and the eighth is 14, and between the eighth and the ninth is 15. It is clear, therefore, that the sequence of consecutive distances increases.
In the case that a pair of consecutive elements at distance d exists, the function must return the position (indexing from 0) of the first element of the pair. Otherwise, the function must return -1. In the previous example, with d=12 the function must return 5, and with d=6 the function must return −1. This is the header:
// Pre: Let n be v.size(). n>=2 and d>=0 and |v[0]-v[1]| < |v[1]-v[2]| < ... < |v[n-2]-v[n-1]|
// Post: If there exists i in {0..n-2} holding |v[i]-v[i+1]| = d, then the function returns this i.
// Otherwise, it returns -1.
int findDistance(int d, const vector<int> &v);
The private test cases try to check that your solution has a logarithmic cost.
Observation You only need to submit the required procedure; your main program will be ignored.
Observation
You can use the function abs in cmath if you wish. Evaluation over 10 points:
- Slow solution: 5 points.
- Fast solution: 10 points.
It is understood that a fast solution is correct, with logarithmic cost and passes all test cases, both public and private. A slow solution is defined as one that is not fast, but it is correct and passes the public test cases.
findDistance(2, [7, 8, 10, 5]) = 1 findDistance(1, [8, 7, 10]) = 0 findDistance(12, [7, 9, 16, 8, -4, 9, 25]) = 3 findDistance(11, [8, 12, 19, 30, 46, 27]) = 2 findDistance(36, [1, 5, 10, 1, -9, -21, -8, -24, -41, -63, -38, -64, -91, -121, -156, -120, -80, -124]) = 14 findDistance(32, [2, 1, -1, -7, 2, -9, -25, -8, -29, -6, 20, 49, 18, 50, 16, 55]) = 12 findDistance(7, [10, 11, 14, 18, 25, 34, 47, 33, 15, 38, 13, -17]) = 3 findDistance(40, [9, 4, -6, -20, -35, -52, -34, -12, -38, -11, 17, -16, -54, -14, 28, 71, 116, 69, 120]) = 12 findDistance(35, [2, 1, 5, 13, 1, 15, -4, -28, 0, 32]) = -1 findDistance(69, [9, 6, 12, 1, 13, 26, 42, 63, 41, 68, 36, 1, -37, 2, -41, 5, -46, 7]) = -1 findDistance(0, [1, 2, 4, 1, -4, -11, -19, -29, -43, -60, -82, -106, -135]) = -1 findDistance(27, [4, 7, 0, -8, 5, 23, 0]) = -1 findDistance(2, [1, 3, -4, -12]) = 0 findDistance(13, [7, 10, 2, -9, -24, -44, -22, -47, -20, 11, -22, 16, 56, 11]) = -1 findDistance(11, [9, 11, 5, -6]) = 2 findDistance(5, [2, 0, -5, -11, -4, -16, -31, -50, -70, -91, -68, -43, -69, -100, -64, -26, -65, -107, -60, -12]) = 1 findDistance(2, [4, 6, -1, -11, -23, -37]) = 0 findDistance(22, [10, 10, 6, -2, 10, 26, 46, 21, 48, 16, -18, -55, -17, 25, 70, 118]) = -1 findDistance(5, [6, 3]) = -1 findDistance(41, [5, 5, 1, 6, -1, -13, 4, 26, 0, 27, 57, 22, 58, 17, -25, 22, 74, 21, 78]) = 12