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

Question

I had an interview in which I am terrible. So now I am trying to find a solution to the issue. 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:

• Each letter represents a positive integer value.

• You add values ​​together except ...

• ... when a value (or the same values ​​are executed) is accompanied by a large value, you subtract the total amount of this run of values.

Examples:

IIX → 8

MCCMIIX → 1808

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

I know that this is not the correct Roman number system, but it really is a question.

I managed to program the working solution on the correct Roman system. But I cannot change it so that it adapts to these new rules, in particular to rule 3. I tried, but to no avail. The way my solution right now, for IIX, it prints 10 instead of the correct answer 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 really appreciated. It would be especially helpful if you could tell me how to change my code. Thanks!

EDIT: I edited the names of the methods to make them clearer.

Answer 1

My trick is working with supposedly small tests you tested.

 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

This is how I would approach the problem:

• Read the string character by character and at each step pay attention to the current character and the previous character .
  • If the current character matches the previous one, increase the execution time by 1.
  • If the current character has a smaller value than the previous one, add the duration * of the previous character to total and reset the length to 1.
  • If the current character has a larger value than the previous one, subtract the duration * of the previous character from the total and reset the execution length to 1.

Answer 3

So no one caught my hint. Then I will try too. I will not go into "IVX" - a thing, because I believe it is 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 does not take into account input validation for brevity. I assume that all input is validated and consists only of allowed characters in accordance with the "rules".

Answer 4

My occupation.

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 most importantly, what I run:

 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

How i did it.

It works for the two 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 the value of "IVX":

"... add values ​​together, except when a value (or SAME values ​​are executed) followed by a larger value, you subtract the result of this 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

Such problems are usually very easy to solve with recursive thinking. The solution might look like this:

 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 a recursive solution is forbidden, in my opinion, it is easier not to recursive this algorithm than to find a procedural one on the first attempt =)

Edit: My results:

MCCMIIX Value: 1808

IIX value is: 8

IVX value: 4

IIVVL Value: 38