See the original problem on HackerRank.
Given a decimal number N between 1 and 3999, 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.
- 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
}
|