Roman Number · Coding Gym

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)).

Input Format

The only input is N.

Constraints

1

<= N <= 4999

Output Format

The corresponding roman number.

Solutions

This is a classical problem admitting several solutions.

A solution in Haskell by [](https://hackerrank.com/massimo_zanibon1):

 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 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);
}