Integer to Roman

Intuitionwhy the numeral rules fit one greedy table

Roman numerals are built from large values toward small values, but six values are special: 4, 9, 40, 90, 400, and 900. Each special value is written as one symbol before another, such as IV or CM. If each ordinary and subtractive form is treated as one value-symbol pair, the conversion rule becomes uniform instead of requiring a separate branch for every decimal place.

Scan those pairs from largest to smallest. Whenever the current value fits inside num, append its symbol and subtract its value. A larger pair must be considered first, because using smaller symbols too early can produce a different spelling: 900 must become CM before 500 and 400 are considered. After the scan, num is zero and the appended symbols are already in Roman numeral order.

Approachone descending list handles ordinary and subtractive forms

1. 1Store the value-symbol pairs in descending order, including 900, 400, 90, 40, 9, and 4 as single entries, because omitting a subtractive pair would force the result into an invalid repeated-symbol form.
2. 2Create an empty result string that will receive symbols from largest to smallest, because appending in scan order avoids a reversal or later rearrangement.
3. 3For each pair, repeatedly check whether its value is at most num, because a symbol such as I, X, or M may be used more than once.
4. 4When the value fits, append its symbol and subtract its value from num, because both operations represent one copy of that Roman component and reduce the remaining number by exactly that component.
5. 5Continue through all pairs in descending order, because choosing a smaller pair before a larger one can destroy a required form such as CM or XL.
6. 6Return the result after the scan, because every integer from 1 to 3999 is covered by the listed ordinary and subtractive values and the remaining num therefore reaches zero.

Complexitythe bounded numeral table keeps both bounds constant

Annotated solutionC++ · greedy scan · the table carries every Roman numeral rule

#include <string>
#include <utility>
#include <vector>

using namespace std;

class Solution {
public:
    string intToRoman(int num) {
        vector<pair<int, string>> values = {
            {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
            {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
            {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}
        };

        string result;
        for (const auto& [value, symbol] : values) {
            while (num >= value) {
                result += symbol;
                num -= value;
            }
        }

        return result;
    }
};

The while loop is important even though many entries are used once. It allows values such as 1000, 100, 10, and 1 to repeat, so 3749 can consume three M symbols and then three C symbols. The subtractive entries do not need separate code: 900 is consumed as CM, 90 as XC, and 4 as IV because those complete forms appear before their smaller components.

The place-value alternativea direct lookup by thousands, hundreds, tens, and ones

A competent alternative is to split num into its thousands, hundreds, tens, and ones digits, then select one prewritten string for each digit. This is merely a different arrangement, not an asymptotic optimisation: both methods use constant time and constant extra space under the stated range. The lookup version makes the four decimal places explicit, while the greedy version generalises more naturally when the numeral rules are represented as value-symbol pairs.

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string intToRoman(int num) {
        const vector<string> thousands = {"", "M", "MM", "MMM"};
        const vector<string> hundreds = {
            "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"
        };
        const vector<string> tens = {
            "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"
        };
        const vector<string> ones = {
            "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"
        };

        string result;
        result += thousands[num / 1000];
        result += hundreds[(num / 100) % 10];
        result += tens[(num / 10) % 10];
        result += ones[num % 10];
        return result;
    }
};

Common mistakestwo wrong code shapes that look plausible