See the original problem on HackerRank.
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)).
The only input is N.
Constraints
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
|
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
|
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)
|
In Haskell, if you want to confuse the reader, you can use the >> bind operator.
1
2
3
4
5
6
7
8
9
10
11
12
13
|
import Data.List
import Data.Maybe
numerals =
[ (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"), (90, "XC"),
(50, "L"), (40, "XL"), (10, "X"), (9, "IX"), (5, "V"), (4, "IV") ]
toRoman 0 = []
toRoman x = ([1 .. (div x y)] >> ry) ++ toRoman (mod x y)
where
(y, ry) = fromMaybe (1, "I") (find ((>=) x . fst) numerals)
main = interact $ toRoman . read
|