Roman Number · Coding Gym

Given a decimal number N between 1 and 4999, find its corresponding Roman numeral.

Roman numerals are formed by the combination of these letters:

1
2
3
4
5
6
7


I=1
V=5
X=10
L=50
C=100
D=500
M=1000

Rules to combine letters:

A letter repeats its value that many times (XXX = 30, CC = 200, etc.). A letter can only be repeated three times (except M).
If one or more letters are placed after another letter of greater value, add that amount (VI = 6 (5+1)).
If a letter is placed before another letter of greater value, subtract that amount (IV = 4(5-1)).

Input Format

The only input is N.

Constraints

1

1 <= N <= 4999

Output Format

The corresponding roman number.

Solutions

This is a classical problem admitting several solutions.

A solution in Haskell by Massimo Zanibon:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


module Main where

import Data.List

fromIntToRoman :: [(Int, String)]
fromIntToRoman
  = [(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")
    ]

convert :: Int -> String
convert 0 = ""
convert x = case find (\(y, ry) -> y <= x) fromIntToRoman of
              Nothing
                -> error "error in the code"
              Just (y, ry)
                -> let str1 = concat $ replicate (div x y) ry
                       rest = mod x y
                   in  str1 ++ (convert rest)

main :: IO ()
main = do
    inputString <- getLine
    putStrLn $ convert $ read inputString

A Rust solution by Alessandro Pezzato

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


fn roman_number(mut n: u32) -> String {
    const TABLE: [(u32, &'static str); 13] = [
        (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"),
    ];

    let mut txt = String::new();

    for &(d, s) in TABLE.iter() {
        while n >= d {
            n -= d;
            txt.push_str(s);
        }
    }

    txt
}

A C++ solution based on binary search:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


#include <map>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

string to_roman(int n)
{
    // defines the correspondence between a decimal number and the Roman symbol
    static const map<int, string> m{
        { 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" },
    };

    string roman;
    while (n)
    {
        auto lb = m.lower_bound(n); // find the symbol
        if (lb == end(m) || lb->first != n)
            lb = prev(lb);
        roman += lb->second;
        n -= lb->first;
    }
    return roman;
}

int main()
{
    int n; cin >> n;
    cout << to_roman(n);
}

A more complex solution, in Rust, that uses only single characters instead of already composed numbers in the table.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50


fn roman_number(mut n: u32) -> String {
    const TABLE: [(u32, char); 7] = [
        (1000, 'M'),
        (500, 'D'),
        (100, 'C'),
        (50, 'L'),
        (10, 'X'),
        (5, 'V'),
        (1, 'I'),
    ];

    let find_next_sub = |y: u32| TABLE.iter().find(|&&x| x.0 == y / 10).unwrap();

    let mut txt = String::new();

    /* This is the current power of ten to subtract */
    let mut u = find_next_sub(TABLE[0].0);

    for &(mut d, s) in TABLE.iter() {
        /* Subtract the number from table and add to string
         * the relative character until n is big enough.
         */
        while n >= d {
            txt.push(s);
            n -= d;
        }

        /* No more to subtract */
        if d == 1 {
            break;
        }

        if d == u.0 {
            u = find_next_sub(d);
        }

        /* Try with the number on the table minus the
         * power of ten in the same order of magnitude.
         */
        d = d - u.0;

        if n >= d {
            txt.push(u.1);
            txt.push(s);
            n -= d;
        }
    }

    txt
}

A couple of solutions in python by Matteo Italia and Giulia Crotti.

The first uses a lookup on all the available patterns:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


n = int(input())
lut = [
    ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"],
    ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"],
    ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"],
    ["", "M", "MM", "MMM", "MMMM"]
]
out = ""
for i in range(3, -1, -1):
    digit = (n // (10**i)) % 10
    out += lut[i][digit]
print(out)

The second defines all the patterns using indexes:

1
2
3
4
5
6
7
8
9


n = int(input())
lut = [(), (0,), (0,0), (0,0,0), (0,1), (1,), (1,0), (1,0,0), (1,0,0,0), (0,2)]
rdigits = "IVXLCDM"
out = "M" * (n//1000)
for i in range(2, -1, -1):
    digit = (n // (10**i)) % 10
    for j in lut[digit]:
        out += rdigits[j+2*i]
print(out)

binary search