Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Strings

Integer to Roman

Medium · Strings · Asked at Amazon, Microsoft, Google

Convert an integer to a Roman numeral (standard form, using IV, IX, XL, XC, CD, CM where needed).

Input

One integer n.

Output

The Roman numeral.

Constraints

Example 1

Input

58

Output

LVIII

Example 2

Input

1994

Output

MCMXCIV

Hints

  1. List the values from big to small, including the subtractive pairs: 1000 M, 900 CM, 500 D, 400 CD, 100 C, …, 4 IV, 1 I.
  2. Greedy: while n ≥ the current value, append its symbol and subtract it.

Approach

With the 13 values (M, CM, D, CD, C, XC, L, XL, X, IX, V, IV, I) in decreasing order, the greedy method is correct: repeatedly take the largest value that still fits. Listing the subtractive pairs as their own symbols removes all special cases. 1994 → M (994) → CM (94) → XC (4) → IV.

Complexity: O(1) time (the numeral has at most 15 symbols)

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int vals[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    string syms[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    string out;
    for (int i = 0; i < 13; i++)
        while (n >= vals[i]) {
            out += syms[i];
            n -= vals[i];
        }
    cout << out << "\n";
    return 0;
}

Python solution

PAIRS = [(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")]
n = int(input())
out = []
for value, sym in PAIRS:
    count, n = divmod(n, value)
    out.append(sym * count)
print("".join(out))

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] vals = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] syms = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 13; i++)
            while (n >= vals[i]) {
                sb.append(syms[i]);
                n -= vals[i];
            }
        System.out.println(sb);
    }
}

Solve Integer to Roman online · All practice problems