SkewDecimal

SRM 128 · 2003-01-06 · by vorthys

Class Name: SkewDecimal

Return Type: String

Method Name: multiply

Arg Types: (string, string)

Problem Statement

A skew decimal numeral is a non-empty string of digits chosen from the set {'0'-'9','X'}. The digits '0'-'9' have their usual meanings, and the digit 'X' means ten (all quotes for clarity only). Not all combinations of digits are valid. In particular,

the leftmost digit must be non-zero, and
no non-zero digit may appear to the right of an 'X'.

For example, "987", "13X", and "X000" are valid skew decimal numerals but "0056", "XX00", and "19X01" are not.

Skew decimal numerals uniquely represent the positive integers, meaning there is a one-to-one mapping between positive integers and skew decimal numerals. For example, the integer 1 is represented by the skew decimal numeral "1" (quotes for clarity only). For each positive integer N, the representation of N+1 can be derived from the representation of N as follows:

If the representation of N contains an 'X', increment the digit to the left of the 'X' and replace the 'X' with '0' (if the 'X' is the leftmost digit, first insert a '0' to its left). [Examples: "89X" plus one is "8X0" and "X00" plus one is "1000".]
Otherwise, increment the rightmost digit. [Example: "12309" plus one is "1230X".]

Incrementing a digit means replacing the digit with the next higher digit (eg, replacing '5' with '6' or replacing '9' with 'X').

What makes skew decimal numerals interesting is that the representations of N and N+1 differ in at most two digits, as opposed to ordinary decimal numerals, where N and N+1 may differ in every digit (eg, 9999 and 10000).

Create a class SkewDecimal containing a method multiply that takes two skew decimal numerals, num1 and num2 (each a String), multiplies the integers they represent, and returns the valid skew decimal numeral representing the resulting integer (also as a String).

Constraints

num1 and num2 will each contain between 1 and 9 characters, inclusive.
Each character in num1 and num2 will be either a digit ('0'-'9') or an uppercase 'X' (quotes for clarity only).
num1 and num2 will be valid skew decimal numerals (ie, leftmost digit is non-zero and no non-zero digits to the right of an 'X').

Examples

"X"
"2"
Returns: "19"

"X" is 10 and "2" is 2, so their product is 20. The skew decimal representation of 20 is "19".

"X00000000"
"X00000000"
Returns: "1111111108888888899"

Maximum possible values.

"3"
"38"
Returns: "111"

"X00"
"902"
Returns: "X00000"

"28"
"38"
Returns: "1108"

"3"
"34"
Returns: "100"

"3" is 3, and "34" is 37, so their product is 111. The skew decimal representation of 111 is "100".

Submissions are judged against all 27 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SkewDecimal with a public method string multiply(string num1, string num2) · 27 test cases · 2 s / 256 MB per case