A historic rail line once had marker posts standing at equally spaced intervals along a perfectly straight stretch of track — consecutive posts always differ by the same fixed amount, which may be positive, negative, or zero, since the posts could have been numbered while walking in either direction. During a renovation, exactly one post — guaranteed to be neither the very first nor the very last post in the row — was taken away for repair, and workers photographed the remaining posts in their original left-to-right order. From that photograph, determine the position value that used to be marked on the missing post.
Line 1: a single integer n — the number of posts remaining in the photograph (the original row had n+1 posts). Line 2: n integers — the remaining posts' position values, in their original left-to-right order.
A single integer: the position value of the removed post.
3 <= n <= 1000 -10^6 <= position value <= 10^6 The n+1 original position values form an arithmetic progression (constant difference between consecutive posts), and exactly one of them — never the first or last — is missing from the given list.
Example 1
Input
4 5 7 11 13
Expected
9
Explanation
The original 5-post progression was 5, 7, 9, 11, 13 with common difference 2. The photograph 5, 7, 11, 13 matches this at the first two positions but then jumps from 7 to 11, skipping 9, so the removed post's value is 9.
Example 2
Input
4 10 7 1 -2
Expected
4
Explanation
The original 5-post progression was 10, 7, 4, 1, -2 with common difference -3. The photograph 10, 7, 1, -2 matches the first two positions but then jumps from 7 to 1, skipping 4, so the removed post's value is 4.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →