Roman to Integer - But using a "different" Roman number system

Question

I had an interview in which I did terribly. So, now I'm trying to find the solution to the question. Here is the interview question:

"We have the following mapping:
M: 1000, D: 500, C: 100, L: 50, X: 10, V: 5, I: 1.

And we have the following rules:

1. Each letter maps to a positive integer value

2. You add the values together, except...

3. ...when a value (or runs of the same values) is followed by a greater value, you subtract the total of that run of values.

Examples:

IIX -> 8

MCCMIIX -> 1808

We are given this Java method: int valueOfRoman(char roman). We have implement the Java method: int romanToInt(String s)"

I know it is not a proper roman number system, but that is the actual question.

I was able to code a working solution to a proper Roman system. But I'm unable to change it so that it adapts to these new rules, particularly Rule 3. I have tried, but with no success. The way my solution is right now, for IIX, it prints 10, instead of the correct answer of 8. Here is my code (I also implemented valueOf for my testing):

static int romanToInt(String s) {
    char curr;
    int currVal;
    char prev;
    int prevVal;

    int total = valueOfRoman(s.charAt(0));

    for (int i = 1; i < s.length(); i++) {
        curr = s.charAt(i);
        currVal = valueOfRoman(curr);

        prev = s.charAt(i-1);
        prevVal = valueOfRoman(prev);

        total += currVal;
        if(currVal > prevVal) {
            total = total - (2*prevVal);
        }

    }
    return total;
}


static int valueOfRoman(char c) {
    if (c == 'M') {
        return 1000;
    } else if (c == 'D') {
        return 500;
    } else if (c == 'C') {
        return 100;
    } else if (c == 'L') {
        return 50;
    } else if (c == 'X') {
        return 10;
    } else if (c == 'V') {
        return 5;
    } else if (c == 'I') {
        return 1;
    } 

    return -1;
}

Any help is really appreciated. Specially useful would be if you can tell me how to modify my code. Thanks!

EDIT: I edited the names of the methods so they are clearer.

Answer 1

My take - works with the admittedly small tests you supplied.

static int rom2int(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    // Total value.
    int total = 0;
    // The most recent.
    char current = s.charAt(0);
    // Total for the current run.
    int run = valueOf(current);

    for (int i = 1; i < s.length(); i++) {
        char next = s.charAt(i);
        int value = valueOf(next);
        if (next == current) {
            // We're in a run - just keep track of its value.
            run += value;
        } else {
            // Up or down?
            if (value < valueOf(current)) {
                // Gone down! Add.
                total += run;
            } else {
                // Gone UP! Subtract.
                total -= run;
            }
            // Run ended.
            run = valueOf(next);
        }
        // Kee track of most recent.
        current = next;
    }
    return total + run;
}

private void test(String s) {
    System.out.println("Value of " + s + " = " + rom2int(s));
}

public void test() {
    test("IVX");
    test("IIVVL");
    test("IIX");
    test("MCCMIIX");
    test("MVVV");
}

prints

Value of IVX = 4 - Odd!!!
Value of IIVVL = 38
Value of IIX = 8
Value of MCCMIIX = 1808
Value of MVVV = 1015

Answer 2

Here's how I'd approach the problem:

• Read the string character by character and during every step note the current character and the previous character.
  • If the current character is the same as the previous, increase the run length by 1.
  • If the current character has a smaller value than the previous, add run length * value of previous character to the total, and reset run length to 1.
  • If the current character has a greater value than the previous, subtract run length * value of previous character from the total, and reset run length to 1.

Answer 3

So, nobody caught my hint. Then I'll give it a try, too. I won't go into the "IVX"- thing because I consider that a syntax error.

int romanToInt( String s ){
    int total = 0;
    int pivot = 0;

    for( int i = s.length()-1; i >= 0; i--){ // We start at the **end**
        int current = valueOfRoman((s.charAt(i));
        if( current >= pivot ){ // We will have at least "I", so it **will** be > pivot for 1st char.
            pivot = current; 
            total += pivot;
        }else{
            total -= current;
        }
    }
    return total;
}

Let's see: IIX

i    char    value    total    pivot   ->   total   pivot
2     X        10       0        0      >      10      10
1     I         1      10       10      <       9      10
0     I         1       9       10      <       8      10

MCCMIIX

i    char    value    total    pivot   ->   total   pivot
6     X        10       0        0     >       10      10
5     I         1      10       10     <        9      10
4     I         1       9       10     <        8      10
3     M      1000       8       10     >     1008    1000
2     C       100    1008     1000     <      908    1000
1     C       100     908     1000     <      808    1000
0     M      1000     808     1000     =     1808    1000

The method leaves out input validation for brevity. I am assuming all input has been checked and consists only of allowed characters according to "the rules".

Answer 4

My take on it.

EDIT CHANGE #2

public class Romans {

private int valueOf(char c) {
    if (c == 'M') {
        return 1000;
    } else if (c == 'D') {
        return 500;
    } else if (c == 'C') {
        return 100;
    } else if (c == 'L') {
        return 50;
    } else if (c == 'X') {
        return 10;
    } else if (c == 'V') {
        return 5;
    } else if (c == 'I') {
        return 1;
    }

    return 0;
}

public int rom2int(String s) {
    int currVal;
    int runValue = 0;
    int repetition = 0;
    int total = 0;
    boolean alreadyAdded = false;
    for (int i = 0; i < s.length(); i++) {
        currVal = valueOf(s.charAt(i));
        if (runValue == 0) {
            runValue = currVal;
            repetition = 1;
            alreadyAdded = false;
        } else if (currVal > runValue) {
            total = total + (currVal - (runValue * repetition));
            repetition = 1;
            runValue = currVal;
            alreadyAdded = true;
        } else if (currVal < runValue) {
            if(!alreadyAdded) {
                total += (runValue * repetition);
            }
            repetition = 1;
            runValue = currVal;
            alreadyAdded = false;
        } else {
            repetition++;
            alreadyAdded = false;
        }
    }

    if (!alreadyAdded) {
        total += (runValue * repetition);
    }

    return total;
}

}

And the main I'm running:

public static void main(String[] args) {
    Romans r = new Romans();
    String[] inputs =  {"MVVV", "IIX","MCCMIIX", "IVX"};
    for(String input : inputs) {
        System.out.println("Value of " + input + " is: " + r.rom2int(input));
    }
}

Outputs:

Value of MVVV is: 1015
Value of IIX is: 8
Value of MCCMIIX is: 1808
Value of IVX is: 9

Answer 5

That's how I did.

It works for those 2 values you mentioned (IIX = 8 and MCCMIIX = 1808):

public static int rom2int(String s)
{
    int currVal = 0, prevVal = 0, subTotal = 0, total = 0;
    for (int i = 0; i < s.length(); i++) {
        currVal = valueOf(s.charAt(i));
        if (currVal > 0) {
            if (prevVal == 0) {
                subTotal = currVal;
            }
            else if (currVal > prevVal) {
                total += (currVal - subTotal);
                subTotal = 0;
            }
            else if (currVal < prevVal) {
                total += subTotal;
                subTotal = currVal;
            }
            else if (currVal == prevVal) {
                subTotal += currVal;
            }
            prevVal = currVal;
        }
    }
    total += subTotal;
    return total;
}

public static int valueOf(char c)
{
    if (c == 'M')
        return 1000;
    if (c == 'D')
        return 500;
    if (c == 'C')
        return 100;
    if (c == 'L')
        return 50;
    if (c == 'X')
        return 10;
    if (c == 'V')
        return 5;
    if (c == 'I')
        return 1;
    return 0;
}

EDIT 1:

Explanation for "IVX" value:

"...add values together except when a value (or runs of the SAME values) is followed by a greater value, you subtract the total of that run of values."

 IVX = 1 5 10
 if  5 > 1 then   5 - 1    = 4
 if 10 > 5 then  10 - 0(*) = 10 (*) we already have used V(5) before, so we discard it.

So the answer for IVX is 14!

Answer 6

My approach would be to break the problem into the following steps:

1. Create a map of the symbols and values (a roman map).
2. Create a store to keep your result.
3. Loop through all the strings from RTL.
4. For each symbol, check that the value of the current symbol is greater than its previous value.
5. If the current symbol is greater than its previous value (e.g IV, where V is the current symbol), then do subtraction (current value minus previous value) and add that to the result; then skip the previous value in the loop.
6. Else; add the value of the current symbol to the result.

Note: An important rule to note is that there can only be 1 prev value in the roman numerals to indicate a reduction.

IV = 4
IIV = invalid
...same with the rest of the numerals (IXCVDM...).

Hope this helps someone in the future.

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        romanMap = { "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000 }
        result = 0;
        index = len(s) - 1;
        while (index >= 0):
            romanValue = s[index];
            prevValue = s[index - 1];
            if ((index > 0) and (romanMap[romanValue] > romanMap[prevValue])):
                result += romanMap[romanValue] - romanMap[prevValue];
                index-= 1;
            else:
                result += romanMap[romanValue];
            index-= 1;
        return result;

You can run the code with the following:

   print(Solution().romanToInt("LVIII"));

Answer 7

this kind of problematics are usually really easy to solve using recursive way of thinking. The solution could look like :

public int rom2int(String s)
{               
    if(s.length() == 0)   
        // no string --> 0
        return  0;
    else if(s.length() == 1)
        // One Character --> Value of Character
        return valueOf(s.charAt(0)); 
    else if((valueOf(s.charAt(0)) > valueOf(s.charAt(1))) ) 
        // The value is NOT followed by a greater value --> We had the value
        return rom2int(s.substring(1, s.length())) + valueOf(s.charAt(0));      
    else if(valueOf(s.charAt(0)) <= valueOf(s.charAt(1)) )
        // The value is followed by a greater (or same) value --> We substract the value
        return rom2int(s.substring(1, s.length())) - valueOf(s.charAt(0));
    else
        // Shouldn't Happen. 0 as neutral element in in a Sum.
        return 0;
}

Even if recursive solution is forbidden, to my mind it is simpler to un-recursive this algorithm than find the procedural one at first try =)

Edit : MY Results :

Value of MCCMIIX is : 1808

Value of IIX is : 8

Value of IVX is : 4

Value of IIVVL is : 38