Roman To Integer Algorithm
The Roman to Integer Algorithm is a computational technique used to convert a Roman numeral string into its equivalent integer value. It is based on the principle that Roman numerals utilize a combination of letters from the Latin alphabet (I, V, X, L, C, D, and M) to represent numerical values. These letters can be combined in specific ways to represent numbers, with the general rule being that smaller symbols are added to larger ones, except when a smaller symbol appears before a larger one, in which case the smaller symbol is subtracted from the larger one. For instance, the Roman numeral "IX" represents the integer 9, as it is the combination of I (1) before X (10), meaning 10 - 1 = 9.
The algorithm for converting Roman numerals to integers typically involves iterating through the input string and identifying the integer value for each character based on a predefined lookup table or dictionary. As the algorithm processes each character in the string, it adds its integer value to a running total, taking into account the subtraction rule mentioned above. To handle the subtraction cases, the algorithm checks if the current Roman numeral is smaller than the one that follows it; if so, the integer value for the current numeral is subtracted from the total, otherwise it is added. Once the entire string has been processed, the resulting total represents the integer value equivalent to the given Roman numeral. This algorithm has a linear time complexity of O(n), where n is the length of the Roman numeral string, making it an efficient method for converting Roman numerals to integers.
package Conversions;
import java.util.*;
public class RomanToInteger {
private static Map<Character, Integer> map = new HashMap<Character, Integer>() {
/**
*
*/
private static final long serialVersionUID = 87605733047260530L;
{
put('I', 1);
put('V', 5);
put('X', 10);
put('L', 50);
put('C', 100);
put('D', 500);
put('M', 1000);
}};
//Roman Number = Roman Numerals
/**
* This function convert Roman number into Integer
*
* @param A Roman number string
* @return integer
*/
public static int romanToInt(String A) {
char prev = ' ';
int sum = 0;
int newPrev = 0;
for (int i = A.length() - 1; i >= 0; i--) {
char c = A.charAt(i);
if (prev != ' ') {
// checking current Number greater then previous or not
newPrev = map.get(prev) > newPrev ? map.get(prev) : newPrev;
}
int currentNum = map.get(c);
// if current number greater then prev max previous then add
if (currentNum >= newPrev) {
sum += currentNum;
} else {
// subtract upcoming number until upcoming number not greater then prev max
sum -= currentNum;
}
prev = c;
}
return sum;
}
public static void main(String[] args) {
int sum = romanToInt("MDCCCIV");
System.out.println(sum);
}
}
