Class Name: TriangleSum
Method Name: computeCrossSum
Parameters: int[], int, int
Returns: int
You are to implement a class TriangleSum, which contains a method
computeCrossSum. The method should create an inverted version of a Pascal-like
triangle who's top row is the int[] input parameter.
Here's how the inverted triangle is constructed. The top row of the triangle
is given to you as the int[] parameter of the method. The row underneath the
top row has one less element than the top row. The ith element of a particular
row is created by summing the ith and (i+1)th elements of the row above it.
This process of creating new rows is repeated until the newly created row has
only 1 element. There will be as many rows as there are elements in the int[]
parameter.
For example, given the int[] [1, 2, 3, 4, 5], the following inverted triangle
would be created.
row 0 1 2 3 4 5
row 1 3 5 7 9
row 2 8 12 16
row 3 20 28
row 4 48
If the int[] [-2, 3, 6, 1, 4, 3] was given, then the following inverted
triangle would be created.
row 0 -2 3 6 1 4 3
row 1 1 9 7 5 7
row 2 10 16 12 12
row 3 26 28 24
row 4 54 52
row 5 106
The specified row and column parameters denote a particular element in the
triangle, the intersection of two diagonals. A diagonal is a set of elements
in the inverted triangle that appear in a line with a slope of 1 or -1. For
example in the above triangle the elements 54-28-12-5-4 form a diagonal. The
elements 3-9-16-28-52 also form a diagonal.
If the int array [1, 2, 3, 4, 5] is given, with a row of 1 and column of 2,
then the intersection is the 7. The diagonals to sum are marked with *'s.
row 0 1 2 *3* *4* 5
row 1 3 5 *7* 9
row 2 8 *12* *16*
row 3 *20* 28
row 4 48
The return value of the function would be, 3+7+16+4+12+20 = 62. Notice that
the 7 was only counted once.
Specifications (TopCoder will validate these):
1. The input int[] will have between 1 and 20 elements (inclusive).
2. Each element of the top row will have a value between -100 and +100
(inclusive).
The method computeCrossSum should return the sum of the elements of the
diagonals that intersect at element at the specified row and column.
The row and column parameters can have any integer value. Columns and rows are
0 based, (the top left element of the inverted triangle is at row 0 and column
0). If there is no number in the triangle at the specified row and column, then
your function should return -1.
The method signature is (be sure your method is public):
int computeCrossSum(int[] toprow, int row, int column)
Examples:
toprow=[1, 2, 3, 4, 5], row=0, col=0 -> 80
toprow=[1, 2, 3, 4, 5], row=2, col=3 -> -1
toprow=[1, 2, 3, 4, 5], row=4, col=0 -> 138
toprow=[-13, 12, 3, 0], row=1, col=1 -> 62
toprow=[-13, 12, 3, 0], row=4, col=0 -> -1
toprow=[-13, 12, 3, 0], row=0, col=1 -> 44
toprow=[5], row=0, col=0 -> 5
toprow=[1, 4, 8, 2, 3, 7, 1, 9, 0, 11, -3, 19, 92, -38, 100, -100, 1, 41]
row=7, col=4 -> 281278