Integer to Roman

Problem: Integer to Roman

The basic idea is to accumulate 1 at each digit (better from bigger to smaller), and deal with different counts of ones differently.

Code in Python:

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        dict = ({'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000})
        ones = ['M', 'C', 'X', 'I']
        fives = ['', 'D', 'L', 'V']
        ans = ""
        for i in xrange(len(ones)):
            count = num / dict[ones[i]]
            if count > 8 and i:
                ans += ones[i] + ones[i-1]
            elif count >= 5 and i:
                ans += fives[i] + ones[i] * (count - 5)
            elif count > 3 and i:
                ans += ones[i] + fives[i]
            else:
                ans += ones[i] * count
            num -= dict[ones[i]] * count
        return ans

A more complicate solution in Java:

public class Solution {
    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < num/1000; i++) {
            sb.append('M');
        }
        num %= 1000;

        if (num >= 900) {
            sb.append("CM");
        } else if (num >= 600) {
            sb.append('D');
            for (int i = 0; i < (num-500)/100; i++) {
                sb.append('C');
            }
        } else if (num >= 500) {
            sb.append('D');
        } else if (num >= 400) {
            sb.append("CD");
        } else {
            for (int i = 0; i < num/100; i++) {
                sb.append('C');
            }
        }
        num %= 100;

        if (num >= 90) {
            sb.append("XC");
        } else if (num >= 60) {
            sb.append('L');
            for (int i = 0; i < (num-50)/10; i++) {
                sb.append('X');
            }
        } else if (num >= 50) {
            sb.append('L');
        } else if (num >= 40) {
            sb.append("XL");
        } else {
            for (int i = 0; i < num/10; i++) {
                sb.append('X');
            }
        }
        num %= 10;

        if (num == 9) {
            sb.append("IX");
        } else if (num >= 6) {
            sb.append('V');
            for (int i = 0; i < num-5; i++) {
                sb.append('I');
            }
        } else if (num == 5) {
            sb.append('V');
        } else if (num == 4) {
            sb.append("IV");
        } else {
            for (int i = 0; i < num; i++) {
                sb.append('I');
            }
        }

        return sb.toString();
    }
}