Thursday, January 5, 2012

Convert integers to roman numbers

Question: write an algorithm to convert an integer into roman number. For example, 1 -> I, 2 -> II, or 4 -> IV.
Solution: in order to solve this problem, we must know the rules of writing roman numerals. For example, I is 1 and V is 5 but IV is not 6 but 4 (5 -1). Moreover, there is no 0 number in roman numeral system. Here is the link to an article about roman numerals if you are unfamiliar with the system.
As you may notice, the roman numeral system consists of several fundamental and unique numbers. They are used in conjunction with rules to create other numbers. Therefore, we just have to cache the unique numbers and apply the rules in order to generate any roman number we want. Lets take a simpler case. Suppose we have to handle only 4 digit number:

void printRomanNumeral3digit(int n)
 {

  int num, i;

   num=n;

         for (i = 0; i < num/1000; i++)
   out.println( "M");

  num = num % 1000;
  switch (num/100)
  {
   case 9:
    out.println( "CM");
    break;
   case 8:
    out.println( "DCCC");
    break;
   case 7:
    out.println( "DCC");
    break;
   case 6:
    out.println( "DC");
    break;
   case 5:
    out.println( "D");
    break;
   case 4:
    out.println( "CD");
    break;
   case 3:
    out.println( "CCC");
    break;
   case 2:
    out.println( "CC");
    break;
   case 1:
    out.println( "C");
    break;
  }

   num = num % 100;
  switch (num/10)
  {
   case 9:
    out.println( "XC");
    break;
   case 8:
    out.println( "LXXX");
    break;
   case 7:
    out.println( "LXX");
    break;
   case 6:
    out.println( "LX");
    break;
   case 5:
    out.println( "L");
    break;
   case 4:
    out.println( "XL");
    break;
   case 3:
    out.println( "XXX");
    break;
   case 2:
    out.println( "XX");
    break;
   case 1:
    out.println( "X");
    break;
  }

   num = num % 10;
  switch (num)
  {
   case 9:
    out.println( "IX");
    break;
   case 8:
    out.println( "VIII");
    break;
   case 7:
    out.println( "VII");
    break;
   case 6:
    out.println( "VI");
    break;
   case 5:
    out.println( "V");
    break;
   case 4:
    out.println( "IV");
    break;
   case 3:
    out.println( "III");
    break;
   case 2:
    out.println( "II");
    break;
   case 1:
    out.println( "I");
    break;
  }
 }


Handling a more general case:
This is the better algo in java (just update cache to handle larger numbers)
public static String int2RomanNum(int intVal)
{
 if (intVal <= 0)
 {
  out.println(  "Roman numbers don't support 0 or negative! Return NULL" );
  return ""; 
 }

 //build hash table of unique values 
 Map<Integer,String> romanMap = new HashMap<Integer, String>();

 romanMap.put(1, "I");
 romanMap.put(1,"I");
 romanMap.put(4,"IV");
 romanMap.put(5,"V");
 romanMap.put(9,"IX");
 romanMap.put(10,"X");
 romanMap.put(40,"XL");
 romanMap.put(50,"L");
 romanMap.put(90,"XC");
 romanMap.put(100,"C");
 romanMap.put(400,"CD");
 romanMap.put(500,"D");
 romanMap.put(900,"CM");
 romanMap.put(1000,"M");

 //the roman value
 String romanResult = "";

 //traverse the list in reverse order 
 List<Integer> keys = new ArrayList<Integer>(romanMap.keySet());
 Collections.sort(keys);
 Collections.reverse(keys);
 Iterator<Integer> it = keys.iterator() ;

 for (; it.hasNext(); )
 {
  //if current number is greater than current key in list
  //add the value corresponded with key to result
  //then subtract the equivalent int value from current number
  int key = it.next();

  while (intVal >= key)
  {   
   int literal = intVal/key;
   if(literal!=0)
    romanResult+=romanMap.get(key);
   intVal = intVal%key;

  }
 }

 return romanResult;
}



Note that Collections.sort(list<>) will not work here and it commented. and sorted result will be :
[90, 900, 1000, 50, 400, 40, 10, 9, 500, 5, 4, 100, 1].

So we have to modify the logic

0 comments:

Post a Comment