integer_to_roman.cc

// Time: O(n) Space: O(1)
class Solution {
public:
  string intToRoman(int num) {
    assert(num >= 1 && num <= 3999);
    string ret;
    char roman[7] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
    int scale = 1000;
    for (int i = 6; i >= 0; i -= 2) {
      int digit = num / scale;
      if (digit == 0); 
      else if (digit <= 3) {
        ret.append(digit, roman[i]);
      } else if (digit == 4) {
        ret += roman[i];
        ret += roman[i + 1]; 
      } else if (digit == 5) {
        ret += roman[i + 1]; 
      } else if (digit <= 8) {
        ret += roman[i + 1]; 
        ret.append(digit - 5, roman[i]);
      } else if (digit == 9) {
        ret += roman[i];
        ret += roman[i + 2]; 
      }   
      num %= scale;
      scale /= 10; 
    }   
    return ret;
  }
};