Statistics

Problem Statement for "SkewDecimal"

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).

Definition

Class:
SkewDecimal
Method:
multiply
Parameters:
String, String
Returns:
String
Method signature:
String multiply(String num1, String num2)
(be sure your method is public)

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

  1. "X"

    "2"

    Returns: "19"

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

  2. "X00000000"

    "X00000000"

    Returns: "1111111108888888899"

    Maximum possible values.

  3. "3"

    "38"

    Returns: "111"

  4. "X00"

    "902"

    Returns: "X00000"

  5. "28"

    "38"

    Returns: "1108"

  6. "56"

    "19"

    Returns: "109X"

  7. "3"

    "34"

    Returns: "100"

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

  8. "10000"

    "513X0"

    Returns: "571084293"

  9. "1"

    "1"

    Returns: "1"

  10. "123456789"

    "987654321"

    Returns: "135480695680705891"

  11. "99887766X"

    "817354X00"

    Returns: "907152942717366542"

  12. "2"

    "5"

    Returns: "X"

  13. "334"

    "2702705"

    Returns: "X00000000"

  14. "2000"

    "5000000"

    Returns: "11109998895"

  15. "2348761"

    "11X00000"

    Returns: "3131676886832X"

  16. "1010101"

    "293487"

    Returns: "329386734962"

  17. "555555555"

    "7777777"

    Returns: "4801093845198942"

  18. "2"

    "4500"

    Returns: "8X00"

  19. "2003"

    "19991492"

    Returns: "44481059915"

  20. "235711"

    "13171923"

    Returns: "3449712754656"

  21. "7"

    "200"

    Returns: "13X0"

  22. "424738X00"

    "195438812"

    Returns: "9223387009552292X"

  23. "1"

    "1"

    Returns: "1"

  24. "987654321"

    "987654321"

    Returns: "1083845609890091310"

  25. "424738X00"

    "195438812"

    Returns: "9223387009552292X"

  26. "1"

    "1"

    Returns: "1"

  27. "987654321"

    "987654321"

    Returns: "1083845609890091310"

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.
This problem was used for: