RevealTriangle | Topcoder Archive

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" }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.