javastringalgorithmroman-numerals

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


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.


Solution

  • 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