Integer to Roman

Mediumhash-tablestringmath
Category: Fundamentals
Companies that ask this question:
AmazonMicrosoftGoogle

Approach

Integer to Roman

Problem Statement

Given an integer, convert it to a roman numeral.

Roman numerals are represented by seven symbols:

| Symbol | Value | |--------|-------| | I | 1 | | V | 5 | | X | 10 | | L | 50 | | C | 100 | | D | 500 | | M | 1000 |

Roman numerals use subtraction notation for 4, 9, 40, 90, 400, and 900:

  • 4: IV (5 - 1)
  • 9: IX (10 - 1)
  • 40: XL (50 - 10)
  • 90: XC (100 - 10)
  • 400: CD (500 - 100)
  • 900: CM (1000 - 100)

Examples

Example 1:

Input: num = 3
Output: "III"

Example 2:

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3

Example 3:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90, IV = 4

Approach

Greedy with Value-Symbol Mapping

Key Insight: Use the largest possible values first (greedy approach).

Algorithm:

  1. Create ordered list of value-symbol pairs (including subtraction cases)
  2. For each value (largest to smallest):
    • While num >= value: append symbol, subtract value
  3. Return the built string

Why include subtraction pairs?

  • Treating 4, 9, 40, 90, 400, 900 as single units simplifies logic
  • Ensures correct subtraction notation

Complexity Analysis

  • Time Complexity: O(1)

    • At most 15 iterations (maximum roman numeral length for 3999)
    • Fixed number of value-symbol pairs (13)

  • Space Complexity: O(1)

    • Result string is at most 15 characters
    • Fixed size mapping array

Visual Intuition

Example: num = 1994

1994 >= 1000 → M, remaining: 994
 994 >= 900  → CM, remaining: 94
  94 >= 90   → XC, remaining: 4
   4 >= 4    → IV, remaining: 0

Result: MCMXCIV

Common Mistakes

  1. Forgetting subtraction cases: Must include IV, IX, XL, XC, CD, CM
  2. Wrong order: Must process largest values first
  3. Using if-else instead of while: Need to use value multiple times (e.g., III)
  4. Not handling 4 and 9: These are special subtraction cases

Related Problems

  • Roman to Integer
  • Integer to English Words
  • Excel Sheet Column Title

Solution

java
1/**
2 * Integer to Roman
3 * Time: O(1) - fixed iterations
4 * Space: O(1) - fixed result size
5 */
6
7class Solution {
8    public String intToRoman(int num) {
9        // Value-symbol pairs in descending order
10        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
11        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
12        
13        StringBuilder result = new StringBuilder();
14        
15        for (int i = 0; i < values.length; i++) {
16            // Use the largest value as many times as possible
17            while (num >= values[i]) {
18                result.append(symbols[i]);
19                num -= values[i];
20            }
21        }
22        
23        return result.toString();
24    }
25}
26
Loading visualizer...