</>Ali · LeetCode
#0012·MediumMath

Integer to Roman

LeetCode #12 · Medium · Math · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Greedy Subtraction

Key insight

Process the number from largest to smallest value. At each step, subtract the largest possible Roman numeral value and append the corresponding symbol. This handles both regular values and the special subtractive cases.

Strategy

  1. 1Check values in descending order (1000, 900, 500, 400, 100, 90, 50, 40,
  2. 2For each value, if num >= value:
  3. 3Repeat until num becomes 0
Time
O(1)
bounded by max value 3999, at most ~15 iterations
Space
O(1)
result string length is bounded
Problem description(from LeetCode)

Roman numerals are represented by seven different symbols: I, V, X, L, C, D, M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 Roman numerals are usually written largest to smallest from left to right. However, there are six special subtractive cases: - I before V (5) or X (10) makes 4 or 9. - X before L (50) or C (100) makes 40 or 90. - C before D (500) or M (1000) makes 400 or 900. Given an integer, convert it to a roman numeral.

Examples

Example 1
Input:
num = 3
Output:
"III"
Note:
L = 50, V = 5, III = 3. Input: num = 1994 Output: "MCMXCIV" Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints

  • •1 <= num <= 3999

C++ Solution

solution.cpp
class Solution {
public:
string intToRoman(int num) {
    string res = "";
    while (num > 0) {
      if (num >= 1000) {
        res += "M";
        num -= 1000;
      } else if (num >= 900) {
        res += "CM";
        num -= 900;
      } else if (num >= 500) {
        res += "D";
        num -= 500;
      } else if (num >= 400) {
        res += "CD";
        num -= 400;
      } else if (num >= 100) {
        res += "C";
        num -= 100;
      } else if (num >= 90) {
        res += "XC";
        num -= 90;
      } else if (num >= 50) {
        res += "L";
        num -= 50;
      } else if (num >= 40) {
        res += "XL";
        num -= 40;
      } else if (num >= 10) {
        res += "X";
        num -= 10;
      } else if (num >= 9) {
        res += "IX";
        num -= 9;
      } else if (num >= 5) {
        res += "V";
        num -= 5;
      } else if (num >= 4) {
        res += "IV";
        num -= 4;
      } else if (num >= 1) {
        res += "I";
        num -= 1;
      }
    }

    return res;
  }
};

More Math problems