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:

74932
1325
457
92
1

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

0)
    
{"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)
    
{"1"}
Returns: {"1" }
2)
    
{"???2", "??2", "?2", "2"}
Returns: {"0002", "002", "02", "2" }
3)
    
{"??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