GuessingNextElement
SRM 387 · 2008-01-09 · by Relja
Problem Statement
An integer arithmetic progression is a sequence defined by two positive integers, p and q, where p is the first element in the sequence, and all other elements are obtained by adding q to the previous element. For example, if p = 1 and q = 2, the sequence would be: 1, 3, 5, 7, ...
An integer geometric progression is a sequence defined by two positive integers, p and q, where p is the first element in the sequence, and all other elements are obtained by multiplying the previous element by q. For example, if p = 3 and q = 2, the sequence would be: 3, 6, 12, ...
You are given a
Constraints
- A will contain between 3 and 50 elements, inclusive.
- Each element of A will be between 1 and 10^6, inclusive.
- A will be sorted in ascending order.
- A will uniquely represent either an arithmetic or geometric progression.
{364,843,1322,1801}
Returns: 2280
This sequence represents an arithmetic progression where p = 364 and q = 479. The next element is 1801 + 479 = 2280.
{315,785,1255,1725,2195,2665}
Returns: 3135
{394,1172,1950,2728,3506,4284,5062,5840}
Returns: 6618
{944,1073,1202,1331,1460,1589,1718,1847,1976,2105}
Returns: 2234
{162,549,936,1323,1710,2097,2484,2871,3258,3645,4032,4419}
Returns: 4806
{33,231,1617,11319,79233}
Returns: 554631
This
{13,117,1053,9477,85293}
Returns: 767637
This sequence represents a geometric progression where p = 13 and q = 9. The next element is 85293 * 9 = 76737.
Submissions are judged against all 56 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GuessingNextElement with a public method int guess(vector<int> A) · 56 test cases · 2 s / 256 MB per case