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
- 1 ≤ n ≤ 3999
Example 1
Input
58
Output
LVIII
Example 2
Input
1994
Output
MCMXCIV
Hints
- 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.
- 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);
}
}