TopCoder problem "DerivativeSequence" used in SRM 322 (Division II Level One)

Problem Statement

Given a sequence of K elements, we can calculate its difference sequence by taking the difference between each pair of adjacent elements. For instance, the difference sequence of {5,6,3,9,-1} is {6-5,3-6,9-3,-1-9} = {1,-3,6,-10}. Formally, the difference sequence of the sequence a₁, a₂, ... , a_k is b₁, b₂, ... , b_k-1, where b_i = a_i+1 - a_i.

The derivative sequence of order N of a sequence A is the result of iteratively applying the above process N times. For example, if A = {5,6,3,9,-1}, the derivative sequence of order 2 is: {5,6,3,9,-1} -> {1,-3,6,-10} -> {-3-1,6-(-3),-10-6} = {-4,9,-16}.

You will be given a sequence a as a int[] and the order n. Return a int[] representing the derivative sequence of order n of a.

Definition

Class:	DerivativeSequence
Method:	derSeq
Parameters:	int[], int
Returns:	int[]
Method signature:	int[] derSeq(int[] a, int n)
(be sure your method is public)

Notes

The derivative sequence of order 0 is the original sequence. See example 4 for further clarification.

Constraints

a will contain between 1 and 20 elements, inclusive.

Each element of a will be between -100 and 100, inclusive.

n will be between 0 and K-1, inclusive, where K is the number of elements in a.

Examples

{5,6,3,9,-1}

Returns: {1, -3, 6, -10 }

The first example given in the problem statement.

{5,6,3,9,-1}

Returns: {-4, 9, -16 }

The second example given in the problem statement.

{5,6,3,9,-1}

Returns: {-38 }

{4,4,4,4,4,4,4,4}

Returns: {0, 0, 0, 0, 0 }

After 1 step, they all become 0.

{-100,100}

Returns: {-100, 100 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6665

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10002&pm=6665

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , Olexiy , Mike Mirzayanov

Problem categories:

Recursion, Simulation