DerivativeSequence

SRM 322 · 2006-10-09 · by soul-net

SRM 322 · 2006-10-09 · by soul-net · Recursion, Simulation

Show categories

Class Name: DerivativeSequence

Return Type: int[]

Method Name: derSeq

Arg Types: (vector<int>, int)

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.

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}
1
Returns: {1, -3, 6, -10 }

The first example given in the problem statement.

{5,6,3,9,-1}
2
Returns: {-4, 9, -16 }

The second example given in the problem statement.

{5,6,3,9,-1}
4
Returns: {-38 }

{4,4,4,4,4,4,4,4}
3
Returns: {0, 0, 0, 0, 0 }

After 1 step, they all become 0.

{0,3,9,18}
3
Returns: {0 }

Submissions are judged against all 50 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DerivativeSequence with a public method vector<int> derSeq(vector<int> a, int n) · 50 test cases · 2 s / 256 MB per case