Problem Statement
I am an archaeologist and I discovered manuscripts from an unknown ancient civilization. It is clear that they used a numerical system similar to that of the Romans. Namely, they had a different letter symbol, a "numeral", to represent each number of the type 10N and 5*10N, for N between 0 and 12 inclusive. To convert a decimal number to their numerals you proceed from left to right processing one decimal digit at a time. If the decimal digit is zero you skip it. If the decimal digit is between 1 and 9 inclusive, and represents k*10N, then it is converted according to the following scheme, where for example purposes A represents 10N, B represents 5*10N, C represents 10N+1:
- 1 <10N symbol> (e.g. A)
- 2 <10N symbol><10N symbol> (e.g. AA)
- 3 <10N symbol><10N symbol><10N symbol> (e.g. AAA)
- 4 <10N symbol><5*10N symbol> (e.g. AB)
- 5 <5*10N symbol> (e.g. B)
- 6 <5*10N symbol><10N symbol> (e.g. BA)
- 7 <5*10N symbol><10N symbol><10N symbol> (e.g. BAA)
- 8 <5*10N symbol><10N symbol><10N symbol>< 10N symbol> (e.g. BAAA)
- 9 <10N symbol><10N+1 symbol> (e.g. AC)
However, we do not know which letter represents which numeral for the civilization in question. Your task is, given a String from those manuscripts representing a numeral, return the smallest positive integer it could represent.
Example Suppose E represents 1, R represents 5, D represents 10, C represents 100, O represents 1,000, P represents 5,000, and T represents 100,000. Then 104,914 will be written as TOPCODER.
Reminder
The rules above completely describe the numerals construction for this problem and in Roman culture. Unfortunately, many people do not use Roman numerals correctly. Here are some common mistakes in using Roman numerals:
- the official Roman numeral for 4 is IV, not IIII
- you can subtract only powers of ten: writing VL for 45 is not allowed - write XLV instead
- subtract only a single letter from a single numeral. Write VIII for 8, not IIX. Write XIX for 19, not IXX
- don't subtract a letter from another letter more than ten times greater. This means you can only subtract I from V or X. Write XCIX for 99, not IC
Definition
- Class:
- RomanNum
- Method:
- convert
- Parameters:
- String
- Returns:
- String
- Method signature:
- String convert(String number)
- (be sure your method is public)
Constraints
- number will consist only of upper-case letters [A-Z] inclusive
- number will have between 1 and 50 characters inclusive
- number will be such that at least one integer will exist which corresponds to it
Examples
"ABC"
Returns: "14"
"ABC" could be interpreted as a number in many different ways, depending on which values the letters represent, e.g. 1011, 109, 16, etc. You need to return the smallest possible, which is 14
"ABA"
Returns: "19"
The only way to interpret this number without using zeros is 19. (otherwise it could be 190 etc., but we are looking for the smallest one)
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
Returns: "4444444444444"
"ABCADEDFFGGGHGYXOP"
Returns: "491923944"
A=108, B=5*108, C=107, D=106, E=105, F=104, G=103, H=102, O=100, P=5*100, X=5*101, Y=101
"ABCA"
Returns: "49"
"BDABCA"
Returns: "499"
"BAACA"
Returns: "79"
"BBCADEDFGGGHGZXOP"
Returns: "21698944"
"ABBCCCDEDFFGFHHHJHKLMK"
Returns: "7319293949"
"BBABCA"
Returns: "299"
"ABAC"
Returns: "191"
"XYZ"
Returns: "14"
This example is the same as the first example, except with different letters.
"ABCB"
Returns: "69"
"XXYZZABCCDEFGGKLOPHH"
Returns: "271747147"
"XLVIII"
Returns: "48"
"VIII"
Returns: "8"
"AA"
Returns: "2"
"AAABCCCDEXXXFGHYYYKLMNZZZV"
Returns: "3818481481"
"TOPCODER"
Returns: "14914"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
Returns: "4444444444444"