All challenges
Medium 0 solved 0% acceptance

Integer to Roman

Write a whole number from 1 to 3999 as a Roman numeral.

What you'll learn

  • Use a value table sorted from largest to smallest
  • Apply a greedy choice repeatedly
  • Handle subtractive pairs as table entries

Problem

Roman numerals use I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 and M = 1000. Symbols are written from largest to smallest and added up, except for six subtractive pairs: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 and CM = 900. Convert n to its standard form, which always uses a subtractive pair instead of four repeated symbols (4 is IV, never IIII).

Implement integer_to_roman(n).

Input

n: The number to convert.

Output

Return the Roman numeral as a string of uppercase letters.

Constraints

1 ≤ n ≤ 3999

Examples

Example 1
Input:
n = 1994

Expected output:
expected = "MCMXCIV"
Input:
long long n = 1994;

Expected output:
std::string expected = "MCMXCIV";
Input:
long n = 1994;

Expected output:
string expected = "MCMXCIV";

Explanation

1000 + 900 + 90 + 4 gives M, CM, XC, IV: "MCMXCIV".

Example 2
Input:
n = 58

Expected output:
expected = "LVIII"
Input:
long long n = 58;

Expected output:
std::string expected = "LVIII";
Input:
long n = 58;

Expected output:
string expected = "LVIII";

Explanation

50 + 5 + 3 gives L, V, III: "LVIII".

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

List the symbols and the six subtractive pairs together, sorted by value.

Hint 2

Repeatedly take the largest value that still fits into what remains.

Hint 3

Try 4, 9 and 3999 by hand to check your table.

Expected complexity

O(1) time, O(1) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.