TopCoder Statistics - Problem Statement

Problem Statement

Given a sequence of integers, s[0],s[1],..,s[n] we can define its difference sequence as the sequence s[1]-s[0], s[2]-s[1], ..., s[n]-s[n-1]. We can similarly generate its second difference sequence as the difference sequence of its difference sequence, and continue generating deeper difference sequences until we get one with length 1.

Here is an example:

seq:         5    -4    12     23
1stdifseq      -9    16    11
2nddifseq         25    -5
3rddifseq            -30

Given a sequence of integers, one useful way to predict the next value in the sequence is by choosing the one that will make the bottom difference of the enlarged sequence be 0. In the example, we would predict -1 as the next value in the sequence -- this would extend the first difference sequence to end with -1 - 23 = -24, the second to end with -35, and the third to end with -30. This would make the single value in the fourth sequence be 0. Given int[] seq, return the predicted value.

Definition

Class:: DifDif
Method:: predict
Parameters:: int[]
Returns:: int
Method signature:: int predict(int[] seq)
(be sure your method is public)

Constraints

seq will contain between 1 and 10 elements, inclusive.
Each element of seq will be between -1000 and 1000, inclusive.

Examples

{5,-4, 12, 23}

Returns: -1

This is the example given above.
{100}

Returns: 100

The first difference sequence of 100,100 is a sequence consisting of one 0.
{1,4,9,16,25,36}

Returns: 49
{-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000}

Returns: 1023000
{-512,-512}

Returns: -512
{111,111,111,111,111}

Returns: 111
{-9}

Returns: -9
{22,12}

Returns: 2
{995,997,999}

Returns: 1001
{13,19,-6,-6,-6,-6,-6,-6,-6}

Returns: -212
{77,75,67,53}

Returns: 33
{2,4,8,16,32}

Returns: 62
{5,10,6,12,8,16,12,24,20}

Returns: -1561
{999,-998,997,-996,995,-994,993,-992,991,-990}

Returns: -1016867
{1000}

Returns: 1000
{1000,-1000,1000,-1000,1000,-1000,1000,-1000,1000,-1000}

Returns: -1023000
{-1000}

Returns: -1000
{0}

Returns: 0
{-115,-654}

Returns: -1193
{700,-395,-296}

Returns: 997
{468,696,-6,-795}

Returns: -828
{641,-909,997,326,226}

Returns: 13026
{-731,-884,668,-198,-439,-50}

Returns: -12268
{-410,-775,753,-690,-12,-742,37}

Returns: 60399
{343,-326,565,860,909,799,468,717}

Returns: 3135
{-579,-905,-43,-712,181,-848,-848,902,868}

Returns: 99588
{-595,970,-243,3,-782,774,159,684,802,-930}

Returns: 384158
{573,-1,602,-589,128,-91,825,-397,772}

Returns: 189864
{406,-884,554,-90,88,-143,890,-934,154,-375}

Returns: -409152
{-256,932,-349,512,-646,705,-744,860,-593}

Returns: -333235
{-56,254,-909,661,-843,919,-542,211,-876,613}

Returns: 716129
{-1000, 1000, -1000, 1000, -1000, 1000, -1000, 1000, -1000, 1000 }

Returns: 1023000
{1, 4, 9, 16, 25, 36 }

Returns: 49
{-4 }

Returns: -4
{1 }

Returns: 1
{-1000, -1000, -1000, -1000, -1000, 1000, 1000, 1000, 1000, 1000 }

Returns: 253000
{1000, -1000 }

Returns: -3000

Statistics

Problem Statement for "DifDif"

Problem Statement

Definition

Constraints

Examples