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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

//! # Description
//!
//! Roman numerals are represented by seven different symbols: `I`, `V`, `X`, 
//! `L`, `C`, `D` and `M`.
//! 
//! ```plain
//! Symbol       Value
//! I            1
//! V            5
//! X            10
//! L            50
//! C            100
//! D            500
//! M            1000
//! ```
//! For example, `2` is written as `II` in Roman numeral, just two one's added 
//! together. `12` is written as `XII`, which is simply `X` + `II`. The number 
//! `27` is written as `XXVII`, which is `XX` + `V` + `II`.
//! 
//! Roman numerals are usually written largest to smallest from left to right. 
//! However, the numeral for four is not `IIII`. Instead, the number four is 
//! written as `IV`. Because the one is before the five we subtract it making 
//! four. The same principle applies to the number nine, which is written as 
//! `IX`. There are six instances where subtraction is used:
//! 
//! `I` can be placed before `V` (`5`) and `X` (`10`) to make `4` and `9`. 
//! `X` can be placed before `L` (`50`) and `C` (`100`) to make `40` and `90`. 
//! `C` can be placed before `D` (`500`) and `M` (`1000`) to make `400` and `900`.
//! Given an integer, convert it to a roman numeral.
//! 
//! Example 1:
//! ```plain
//! Input: num = 3
//! Output: "III"
//! Explanation: 3 is represented as 3 ones.
//! ```
//! 
//! Example 2:
//! ```plain
//! Input: num = 58
//! Output: "LVIII"
//! Explanation: L = 50, V = 5, III = 3.
//! ```
//! 
//! Example 3:
//! ```plain
//! Input: num = 1994
//! Output: "MCMXCIV"
//! Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
//! ```
//! 
//! Constraints:
//! 
//! - `1 $\leqslant$ num $\leqslant$ 3999`
//! 
//! Sources: <https://leetcode.com/problems/integer-to-roman/>

////////////////////////////////////////////////////////////////////////////////

/// Integer to Roman
///
/// # Arguments
/// * `num` - input integer
pub fn int_to_roman(num: i32) -> String {
 convert(num)   
}

fn convert(n: i32)->String {
    let mut num = n;
    let roman_labels = vec!["I", "V", "X", "L", "C", "D", "M"];
    let mut roman_index: usize = 0;
    let mut output: Vec<&str> = vec![];
    while num > 0 {
        let last = num % 10;
        num = num / 10;
        if roman_index < roman_labels.len() {
            match last {
                1..=3 => {
                    for _ in 0..last {
                        output.insert(0, roman_labels[roman_index]);
                    }
                }
                4 => {
                    output.insert(0, roman_labels[roman_index]);
                    output.insert(1, roman_labels[roman_index + 1]);
                }
                5..=8 => {
                    output.insert(0, roman_labels[roman_index + 1]);
                    for _ in 0..(last - 5) {
                        output.insert(1, roman_labels[roman_index]);
                    }
                }
                9 => {
                    output.insert(0, roman_labels[roman_index]);
                    output.insert(1, roman_labels[roman_index + 2]);
                }
                _ => (),
            }

            roman_index += 2;
        } else {
            for _ in 0..(last - 1) {
                output.insert(0, roman_labels[roman_labels.len() - 1]);
            }
        }
    }

    output.as_slice().join("")
}