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 articleabout 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. Let's take a look at the implementation below in C++

#include<iostream>
#include<map>
#include<string>
using namespace std;

string int2RomanNum(int intVal)
{
   if (intVal <= 0)
   {
      cout << "Roman numbers don't support 0 or negative! Return NULL" << endl;
      return ""; 
   }

   //build hash table of unique values 
   map valueMap;

   valueMap[1] = "I";
   valueMap[4] = "IV";
   valueMap[5] = "V";
   valueMap[9] = "IX";
   valueMap[10] = "X";
   valueMap[40] = "XL";
   valueMap[50] = "L";
   valueMap[90] = "XC";
   valueMap[100] = "C";
   valueMap[400] = "CD";
   valueMap[500] = "D";
   valueMap[900] = "CM";
   valueMap[1000] = "M";

   //the roman value
   string romanResult = "";

   //traverse the list in reverse order 
   map::reverse_iterator it;
   
   for (it = valueMap.rbegin(); it != valueMap.rend(); it++)
   {
      //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
      while (intVal >= it->first)
      {
         romanResult = romanResult + it->second;
         intVal = intVal - it->first;
      }
   }

   return romanResult;
}

 

Explanation: our method accepts an integer as parameter and return a string that contains the roman number equivalent to that integer.

1. First we check the parameter to see if it is equal or less than 0. Because there is no 0 or negative roman numbers, we return an empty string after printing out the warning.
2. Next, we build a hash table of unique roman numbers which are then combined to create other numbers.
3. The heart of this method consists of two loops. The "for" loop runs through the hash table from bottom to top (largest number to smallest number). At each number in the hash table, we run the "while" loop to construct the roman number. This while loop will run until the integer is less than the current number in the hash table. And for every iteration in the while loop we add the current roman number to the returned string. For example, if our integer is 35, at the 10 or X position in the hash table, the while loop will kick in and add XXX into our string. And then the for loop continues at the 5 or V position, letting the while loop add V into our string.

Example: let's say we want to convert the integer 430 into its equivalent roman number. Here is how the method runs:

1. First "for" loop's iteration, intVal = 430 and it->first = 1000. No while loop because intVal is less than it->first.
2. Second iteration, intVal = 430 and it->first = 900. No while loop.
3. Third iteration, intVal = 430 and it->first = 500. No while loop.
4. Fourth iteration, intVal = 430 and it->first = 400. Enter while loop:romanResult = CD and intVal = 30. Because intVal is less than it->first after the first "while" iteration, the while loop exits.
5. Fifth iteration, intVal = 30 and it->first = 100. No while loop.
6. Sixth iteration, intVal = 30 and it->first = 90. No while loop.
7. Seventh iteration, intVal = 30 and it->first = 50. No while loop.
8. Ninth iteration, intVal = 30 and it->first = 40. No while loop.
9. Tenth iteration, intVal = 30 and it->first = 10. Enter while loop: 1) intVal = 20 and romanResult = CDX, 2) intVal = 10 and romanResult = CDXX, and 3) intVal = 0 and romanResult = CDXXX. The while loop exits after that because intVal is less than it->first.
10. Nothing happens in the last four iterations because intVal is 0. Thus, the final result is romanResult = CDXXX

Thank you for reading and until next time :)