# Roman Number

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:

1. A letter repeats its value that many times (XXX = 30, CC = 200, etc.). A letter can only be repeated three times (except M).
2. If one or more letters are placed after another letter of greater value, add that amount (VI = 6 (5+1)).
3. 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 #include #include #include #include using namespace std; string to_roman(int n) { // defines the correspondence between a decimal number and the Roman symbol static const map 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) 
We've worked on this challenge in these gyms: modena  padua  milan