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.

Buitenzorg

It seems a working solution to me, what's the issue? Is there an input which produces an unwanted output? – Scission

The way my solution is right now, for IIX, it prints 10, instead of the correct answer of 8. – Buitenzorg

You seem to assume that every run is 2 long, which isn't guaranteed. You should keep track of how long the current run of identical digits is. – Talich

@Talich The number can be IIIIX, and the answer should be 6 – Buitenzorg

What value should "IVX" produce? – Unsound

Hint : start from the right. – Enslave

More worked examples please. If you can't solve a problem on paper, then you can't solve it with a computer. – Assured

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

Unsound

@Buitenzorg - A bit strange actually - it interprets it like this - it sees "IV" as (-1 + ...) and "VX" as (-5 + ...) resulting in 10 - 1 - 5 = 4? ... when a value (or runs of the same values) is followed by a greater value, you subtract the total of that run of values. – Unsound

I thought the emphasis of "runs of the same values" was on "same". But I'm starting to question myself – Buitenzorg

@Buitenzorg - I've asked OP for clarification. – Unsound

@Unsound I read it as same in the case of IVX (V-I) + (X - V) – Sansen

@Unsound I'm the OP. The interviewer didn't address that example, so I'm not sure – Buitenzorg

@Buitenzorg - Ooops! Ok so your call then - is my code a perfect implementation of your rules - despite the unexpected result of "IVX" or am I doomed to a "-1" for being weird? :) – Unsound

@Buitenzorg - What about "IIVVL". I get 38 - meaning -2 + -10 + 50 = 38. – Unsound

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.

Talich

How should "IVX" threated? Like a (10-5)-1 or like a 1+(10-5) ? – Scission

@Jac_opo That's a good question, but according to the rules OP specified IVX should be (5-1)+(10-5) = 9 – Talich

"when a value (or runs of the same values) is followed by a greater value". So, for IVX, the answer should be (5-1)+(10-5) – Buitenzorg

What happens if you end up with a stream of equal numbers? Example: MVVV in your approach there no adding when the current character is the same as the previous – Sansen

@gigaxiola Yes, I left off the starting and the finishing moves to concentrate on the logic of the main loop. But these aren't very hard to work out really, you start out with everything set to zero, and any leftovers at the end you add to the total. I deliberately didn't want to post a full solution. – Talich

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

Enslave

How is this any different from what I posted? Apart from doing it back to front and storing a constantly updated provisional total rather than the length of a run? – Talich

Exactly. You named the difference. My solution does not need to keep track of run length. Personally, I find this most readable and simple. @Talich – Enslave

I don't but fair enough. :) – Talich

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

Sansen

@Jean the third input yes. (Deleting until fixing) – Sansen

@Jean-FrançoisSavard The last one is correct, if you read the rules carefully. – Talich

What should be the correct output of "IVX"? I'm starting to question myself. – Buitenzorg

@Buitenzorg I think I figured it out.. And I believe the answer for IVX should be 9 – Sansen

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!

Angelita

14. Is that what you expect? – Angelita

There is no mention of "discarding previously used values" – Sansen

That's explicit by the word "EXCEPT", or isn't? – Angelita

add values together except when..... infers the ADDING part not the SUBSTRACTING part.. Anyway the instructions are ambiguous so yours is a correct answer and mine is a correct answer ;) – Sansen

So this is not an algorithm problem. It's a text interpretation problem! – Angelita

@Angelita reminds me of: "Buy milk at the superstore, and if you see eggs buy 12" .... The guy brings 12 cartons of milk. – Sansen

And is that wrong? Both answers are correct, don't you think? – Angelita

It should start with: "Schrödinger goes to the supermaket..." – Sansen

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"));

Lyford

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

Camey

1. string is not a valid object. 2. You are missing a couple parenthesis. 3. If no condition match nothing will be returned, therefore it won't compile. – Nicks

4. The logic is wrong, tested it and failed at first use case (IIX) even after fixing the compilation errors. – Nicks

This is, like the mention "could look like" a proposal of algorithm. But I agree this is not perfect. I changed few details, still as algorithm, as I don't have a dev environnement on this device. The fact is : Does reccursive way can solve this? I think (after few improvments). Did anybody propose it before ? No. Is it simpler? Yes. – Camey

Done. If you can compile it and test it I would like to see if my blind code is valid :) – Camey

Already did :P And sorry it is not valid. However it seems the OP is not even sure anymore what is the desired output so it's hard to have something correct. – Nicks

The advantage of the recursive way is that each return is a direct translation of the rule. If my conditions are correct and my translation correct, the output is correct, no side effect. What is unvalid? – Camey

After testing; my code compiles and return the good result for the 2 numbers posted (and I updated for result of other values). Why have I got -2? Does reccursivness affraid voters? – Camey

I Really want to know Why I was downvoted as my solution give exactly the same result as the Fildor One and OldCurmudgeon one. In wich way my solution can be estimated Irrelevant, ineleguant or anything else to be downvoted? – Camey