TopCoder problem "RevealTriangle" used in SRM 404 (Division I Level One , Division II Level Two)

Problem Statement

Suppose there is a triangle of digits like the following:

Each digit, with the exception of those in the top row, is equal to the last digit of the sum of its upper and upper-right neighboring digits.

You will be given a String[] questionMarkTriangle containing a triangle where only one digit in each row is known and all others are represented by '?'s (see example 0 for clarification). Each element of questionMarkTriangle represents a row of the triangle, and the rows are given from top to bottom. Each element contains exactly one digit ('0'-'9') and the remaining characters are all '?'s. Restore the triangle and return it as a String[] without '?'s.

Definition

Class:	RevealTriangle
Method:	calcTriangle
Parameters:	String[]
Returns:	String[]
Method signature:	String[] calcTriangle(String[] questionMarkTriangle)
(be sure your method is public)

Constraints

questionMarkTriangle will contain between 1 and 50 elements, inclusive.

Element i (0 indexed) of questionMarkTriangle will contain exactly n-i characters, where n is the number of elements in questionMarkTriangle.

Each element of questionMarkTriangle will contain exactly one digit ('0'-'9') and all others characters will be '?'s.

Examples

{"4??", 
 "?2", 
 "1"}

Returns: {"457", "92", "1" }

Let's substitute '?'s with unknown variables:

4ab 
c2 
1

Having done that, we start solving for the variables from the bottom to the top. First, we know that the last digit of (c + 2) is 1. Therefore, c must be 9:

4ab 
92 
1

Now we know that the last digit of (4 + a) is 9, which means a is 5:

45b 
92 
1

And, finally, the last digit of (5 + b) is 2, so b is 7.

{"1"}

Returns: {"1" }

{"???2", "??2", "?2", "2"}

Returns: {"0002", "002", "02", "2" }

{"??5?", "??9", "?4", "6"}

Returns: {"7054", "759", "24", "6" }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12176&pm=8215

Writer:

boba5551

Testers:

PabloGilberto , Yarin , Olexiy , ivan_metelsky

Problem categories:

Simple Math