Decimal to Roman conversion

You are twenty minutes into an Amazon phone screen when the interviewer says, "Let's talk about Roman numerals." They type a function signature into the shared editor and ask you to convert an integer like 1994 into its Roman numeral form. This problem, also known as "Integer to Roman" on other platforms, is a favorite at companies like Amazon, Apple, and Salesforce because it tests your ability to design a clean mapping strategy and apply greedy logic under pressure.

TL;DR

Build a mapping of values to Roman numeral symbols in descending order, including all six subtractive combinations (IV, IX, XL, XC, CD, CM). Iterate through this mapping, and for each entry, append the symbol to a result string as many times as the value fits into the remaining number. This greedy approach runs in O(1) time and O(1) space because the input is bounded between 1 and 3999.

Why This Problem Matters

Decimal to Roman conversion tests two skills that come up repeatedly in interviews: building structured mappings and applying a greedy strategy. The greedy pattern here, where you always pick the largest value that fits, is the same one you will use in change-making problems, interval scheduling, and activity selection. Getting comfortable with this problem gives you a template that transfers directly to harder greedy problems.

Roman Numerals: The Rules

Roman numerals use seven base symbols, each with a fixed value:

Three rules govern how these symbols combine:

Rule 1: Additive notation. Place symbols from largest to smallest and sum their values. For example, VII = 5 + 1 + 1 = 7.

Rule 2: Subtractive notation. When a number starts with 4 or 9 at any place value, a smaller symbol precedes a larger one to indicate subtraction. Only six subtractive combinations are valid:

Rule 3: Repetition limits. Symbols for powers of 10 (I, X, C, M) can appear up to three times in a row. Symbols for 5, 50, and 500 (V, L, D) never repeat. If you need four of a power-of-ten symbol, you must use the subtractive form instead (IIII is wrong; IV is correct).

Understanding the Problem

Given: An integer num where 1 ≤ num ≤ 3999 Return: The Roman numeral representation as a string

Here are two examples that exercise different parts of the mapping:

intToRoman(58) returns "LVIII" because 58 = 50 + 5 + 1 + 1 + 1 = L + V + I + I + I.

intToRoman(1994) returns "MCMXCIV" because 1994 = 1000 + 900 + 90 + 4 = M + CM + XC + IV.

The second example shows why the subtractive combinations are essential. Without them, you would have no way to express 900 or 4 in standard Roman numeral form.

Solution Approach

The insight is that Roman numeral construction is inherently greedy. At each step, you pick the largest symbol whose value still fits into the remaining number, subtract that value, and repeat until nothing is left.

To make the greedy strategy handle subtractive cases automatically, include all 13 value-symbol pairs in your mapping, sorted from largest (1000) to smallest (1). When the algorithm encounters a remaining value of 900, it matches CM before it ever reaches D or C, so the subtractive notation falls out naturally with no special-case logic.

Tracing Through 58

Let's walk through intToRoman(58) step by step.

Phase 1: Find the largest fit. Starting from 1000 and working down, the first value that fits into 58 is 50. Append "L" and subtract 50.

Phase 2: Continue with the remainder. Now num = 8. The largest value that fits is 5. Append "V" and subtract 5, leaving num = 3.

Phase 3: Handle the rest. With num = 3, the only value that fits is 1. The inner while loop appends "I" three times, reducing num to 0.

The final result is "LVIII".

Tracing Through 1994

The number 1994 exercises four different entries in the mapping table, including two subtractive pairs:

Each step picks the largest available value. The subtractive pairs CM (900) and IV (4) are matched automatically because they appear in the mapping before the smaller values they are composed of.

Implementation

Prefer a different language? Jump to solutions in other languages.

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

    StringBuilder roman = new StringBuilder();

    for (int i = 0; i < values.length; i++) {
      while (num >= values[i]) {
        num -= values[i];
        roman.append(symbols[i]);
      }
    }

    return roman.toString();
  }
}

The two parallel arrays define the complete mapping in descending order. The outer for loop walks through each value-symbol pair, and the inner while loop handles repeated symbols (like the three I symbols in 58). Once num reaches zero, the loop exits and the StringBuilder holds the finished Roman numeral.

Why Two Parallel Arrays?

You might wonder why we use two arrays instead of a HashMap. The answer is that order matters. The greedy algorithm must process values from largest to smallest, and a HashMap provides no ordering guarantees. Parallel arrays (or a list of tuples in other languages) give us explicit control over iteration order, which is exactly what the greedy strategy demands.

Complexity Analysis

Time Complexity: O(1)

The outer loop iterates over 13 entries, and for any value in the range [1, 3999], the inner while loop runs at most 3 times per entry. The total number of iterations is bounded by a constant regardless of the input, so the time complexity is O(1).

If the constraint were lifted to allow arbitrarily large numbers, you would need to extend the mapping table. In that generalized case the time complexity would be O(log n) because the number of Roman numeral symbols grows logarithmically with the input value.

Space Complexity: O(1)

The mapping table has a fixed size of 13 entries, and the output string is at most 15 characters long (3999 = "MMMCMXCIX"). Both are bounded by constants.

Common Pitfalls

1. Forgetting the subtractive pairs. If your mapping only includes the seven base symbols (I, V, X, L, C, D, M), the algorithm will produce "IIII" instead of "IV" for the value 4. Always include all 13 entries.

2. Wrong ordering. If the mapping is not sorted in strictly descending order, the greedy selection breaks. For example, placing IV before V would cause 5 to be encoded as "IVI" instead of "V".

3. Using string concatenation in a loop (Java). Each += on a String allocates a new object. Use StringBuilder to avoid quadratic character copying.

4. Off-by-one in the constraint. The valid range is 1 to 3999 inclusive. Passing 0 or a negative number is undefined, and 4000 or above cannot be expressed in standard Roman numerals.

Interview Tips

When you get this problem in an interview, start by writing out the 13 value-symbol pairs on the whiteboard or in a comment. This shows the interviewer you understand both the additive and subtractive rules without needing to be told.

Walk through a concrete example like 1994 to validate your approach before writing code. Interviewers appreciate seeing you verify the algorithm on a non-trivial input rather than jumping straight into implementation.

If time permits, mention the alternative place-value approach where you precompute separate arrays for ones, tens, hundreds, and thousands and index into them directly. It eliminates the inner while loop but uses more memory and is harder to extend. Knowing both approaches demonstrates range.

Solutions in Other Languages

Python

class Solution:
    def int_to_roman(self, num: int) -> str:
        roman_numerals = [
            (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')
        ]

        result = []
        for value, symbol in roman_numerals:
            while num >= value:
                result.append(symbol)
                num -= value
        return ''.join(result)

JavaScript

class Solution {
  intToRoman(num) {
    const romanNumerals = [
      { value: 1000, symbol: 'M' },
      { value: 900, symbol: 'CM' },
      { value: 500, symbol: 'D' },
      { value: 400, symbol: 'CD' },
      { value: 100, symbol: 'C' },
      { value: 90, symbol: 'XC' },
      { value: 50, symbol: 'L' },
      { value: 40, symbol: 'XL' },
      { value: 10, symbol: 'X' },
      { value: 9, symbol: 'IX' },
      { value: 5, symbol: 'V' },
      { value: 4, symbol: 'IV' },
      { value: 1, symbol: 'I' }
    ];

    let result = '';
    for (const { value, symbol } of romanNumerals) {
      while (num >= value) {
        result += symbol;
        num -= value;
      }
    }
    return result;
  }
}

TypeScript

class Solution {
  intToRoman(num: number): string {
    const romanNumerals: { value: number; symbol: string }[] = [
      { value: 1000, symbol: 'M' },
      { value: 900, symbol: 'CM' },
      { value: 500, symbol: 'D' },
      { value: 400, symbol: 'CD' },
      { value: 100, symbol: 'C' },
      { value: 90, symbol: 'XC' },
      { value: 50, symbol: 'L' },
      { value: 40, symbol: 'XL' },
      { value: 10, symbol: 'X' },
      { value: 9, symbol: 'IX' },
      { value: 5, symbol: 'V' },
      { value: 4, symbol: 'IV' },
      { value: 1, symbol: 'I' }
    ];

    let result = '';
    for (const { value, symbol } of romanNumerals) {
      while (num >= value) {
        result += symbol;
        num -= value;
      }
    }
    return result;
  }
}

C++

#include <string>
#include <vector>

class Solution {
public:
  std::string intToRoman(int num) {
    std::vector<std::pair<int, std::string>> romanMap = {
      {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"}
    };

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

Go

func (s *Solution) IntToRoman(num int) string {
    values := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
    symbols := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}

    result := ""
    for i := 0; i < len(values); i++ {
        for num >= values[i] {
            result += symbols[i]
            num -= values[i]
        }
    }
    return result
}

Scala

class Solution {
  def intToRoman(num: Int): String = {
    val romanNumerals = List(
      (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")
    )

    var number = num
    val result = new StringBuilder

    for ((value, symbol) <- romanNumerals) {
      while (number >= value) {
        result.append(symbol)
        number -= value
      }
    }

    result.toString()
  }
}

Kotlin

class Solution {
  fun intToRoman(num: Int): String {
    val values = intArrayOf(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)
    val symbols = arrayOf("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I")

    val roman = StringBuilder()
    var remaining = num

    for (i in values.indices) {
      while (remaining >= values[i]) {
        remaining -= values[i]
        roman.append(symbols[i])
      }
    }

    return roman.toString()
  }
}

Ruby

class Solution
  def int_to_roman(num)
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']

    roman = ''

    values.each_with_index do |value, i|
      while num >= value
        num -= value
        roman += symbols[i]
      end
    end

    roman
  end
end

Rust

pub fn int_to_roman(mut num: i32) -> String {
    let values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
    let symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];

    let mut roman = String::new();

    for i in 0..values.len() {
        while num >= values[i] {
            num -= values[i];
            roman.push_str(symbols[i]);
        }
    }

    roman
}

Swift

func intToRoman(_ num: Int) -> String {
    let values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    let symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]

    var num = num
    var result = ""

    for i in 0..<values.count {
        while num >= values[i] {
            num -= values[i]
            result += symbols[i]
        }
    }

    return result
}

C#

using System.Text;

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

        var roman = new StringBuilder();

        for (int i = 0; i < values.Length; i++) {
            while (num >= values[i]) {
                num -= values[i];
                roman.Append(symbols[i]);
            }
        }

        return roman.ToString();
    }
}

Dart

class Solution {
  String intToRoman(int num) {
    List<int> values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
    List<String> symbols = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I'];

    StringBuffer roman = StringBuffer();
    int remaining = num;

    for (int i = 0; i < values.length; i++) {
      while (remaining >= values[i]) {
        remaining -= values[i];
        roman.write(symbols[i]);
      }
    }

    return roman.toString();
  }
}

PHP

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

        $roman = '';

        for ($i = 0; $i < count($values); $i++) {
            while ($num >= $values[$i]) {
                $num -= $values[$i];
                $roman .= $symbols[$i];
            }
        }

        return $roman;
    }
}

Related Problems

Once you have this problem down, try these related challenges to strengthen your number-to-string conversion skills:

• Roman to Integer (Problem 160) - The reverse operation, parsing a Roman numeral string back into an integer
• Pattern-Driven String Matcher - Another problem that exercises structured string building from rules
• Digit Reversal with Overflow Guard - Tests integer manipulation with boundary awareness

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies.