RLESum | Topcoder Archive

Problem Statement

An RLE compressed number is uncompressed as follows. Replace each occurrence of the substring "[k]c" (quotes for clarity), where k is a positive integer without leading zeroes and c is a single digit, with k consecutive occurrences of c. For example, "12[3]3[2]4[5]1" uncompresses to "123334411111". "123[2]3441[3]11" uncompresses to the same number.

Note that uncompression is not recursive; brackets are not allowed to be nested.

You are given two RLE compressed numbers a and b and String[] k. Uncompress a and b, and add them together. Return a int[], the i-th element of which is the k[i]-th digit of the sum. The 0-th digit is the rightmost digit, the 1-st digit is the next digit to the left, etc. If there are not enough digits, the corresponding element must be equal to 0.

Definition

Class:: RLESum
Method:: getDigits
Parameters:: String, String, String[]
Returns:: int[]
Method signature:: int[] getDigits(String a, String b, String[] k)
(be sure your method is public)

Constraints

a and b will contain only digits ('0'-'9') and brackets ('[' and ']').
a and b will each contain between 1 and 50 characters, inclusive.
a and b will each be an RLE compressed number that uncompresses to a valid positive integer with no extra leading zeroes.
a and b, when uncompressed, will each contain no more than 10^18 digits.
k will contain between 1 and 50 elements, inclusive.
Each element of k will be an integer between 0 and 10^18, inclusive, without extra leading zeroes.

Examples

```
"[12]3"
```
```
"[3]1[3]2[3]3"
```
```
{"12", "11", "10", "9", "8","7","6","5","4","3","2","1","0"}
```
```
Returns: {0, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6 }
```
a decompresses to 333333333333, and b decompresses to 111222333. Their sum is 333444555666. We return all of its digits, and also 0 for the 12-th digit which doesn't exist.

"[5]9"

"[5]9"

{"5", "0", "1"}

Returns: {1, 8, 9 }

"123456789"

"987656789"

{"10", "9", "1", "3", "1", "2"}

Returns: {0, 1, 7, 3, 7, 5 }

Note that k need not be sorted, and its elements can be equal to each other.

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.