Problem

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

Analysis

See http://bangbingsyb.blogspot.com/2014/11/leetcode-integer-to-roman.html

Time complexity: O(13*3) = O(1)

Solution

// I: 1
// IV: 4
// V: 5
// IX: 9
// X: 10
// XL: 40
// L: 50
// XC: 90
// C: 100
// CD: 400
// D: 500
// CM: 900
// M: 1000

class Solution {
public:
    string intToRoman(int num) {
        // build the dictionary to value maps
        string dict[13] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int val[13] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string ret;
        int remain = num;
        
        // build the roman results from interger
        for(int i=0; i<13; i++){ if(remain >= val[i]){
                int count = remain/val[i];
                remain = remain%val[i];
                
                for(int j=0; j<count; j++){
                    ret.append(dict[i]);
                }
            }
            
            if(remain == 0) break;
        }
        
        return ret;
    }
};