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 vector 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
vector without '?'s.
DEFINITION
Class:RevealTriangle
Method:calcTriangle
Parameters:vector
Returns:vector
Method signature:vector calcTriangle(vector questionMarkTriangle)
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" }
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)2010, TopCoder, Inc. All rights reserved.