Convert an integer to a roman numeral (Integer to Roman)

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Thoughts:
Not a hard problem. Only tricky point is that 4 is “IV” not “IIII”, 9 is “IX” not “VIIII” or “VIV”. First, we might think the bases are { 1000, 500, 100, 50, 10, 5, 1}, but if we use bases { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }, this problem would become really easy.

Code (C++):

class Solution {
public:
    string intToRoman(int num) {
        setup();
        string s;
        for(map<int, string>::reverse_iterator it = romanMap.rbegin();
            it != romanMap.rend(); ++it) {
            while(num >= it -> first) {
                s += it -> second;
                num -= it -> first;
            }
        }
        return s;
    }
    
private:
    map<int, string> romanMap;
    
    void setup() {
        romanMap[1000] = "M";
        romanMap[900] = "CM";
        romanMap[500] = "D";
        romanMap[400] = "CD";
        romanMap[100] = "C";
        romanMap[90] = "XC";
        romanMap[50] = "L";
        romanMap[40] = "XL";
        romanMap[10] = "X";
        romanMap[9] = "IX";
        romanMap[5] = "V";
        romanMap[4] = "IV";
        romanMap[1] = "I";
    }
};

Code (Java):

public class Solution {
	private static int[] bases = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9,
			5, 4, 1 };
	private static HashMap<Integer, String> map = new HashMap<Integer, String>();

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

	public String intToRoman(int num) {
		setup();
		String result = new String();
		for (int i : bases) {
			while (num >= i) {
				result += map.get(i);
				num -= i;
			}
		}
		return result;
	}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: