Medium Difficulty
Integer to Roman

Hash Table

Math

String

medium

## Integer to Roman

To solve the problem of converting an integer to a Roman numeral, we can create a lookup table that maps each symbol to its corresponding value. We then iterate through the lookup table in descending order, subtracting the largest possible value from the given number and appending the corresponding symbol to the result. We repeat this process until the number becomes zero.

Here's implementation of the algorithm:

``````function intToRoman(num) {
const symbols = {
M: 1000,
CM: 900,
D: 500,
CD: 400,
C: 100,
XC: 90,
L: 50,
XL: 40,
X: 10,
IX: 9,
V: 5,
IV: 4,
I: 1,
};

let roman = "";

for (const symbol in symbols) {
while (num >= symbols[symbol]) {
roman += symbol;
num -= symbols[symbol];
}
}

return roman;
}``````

In this solution, we define the `symbols` object as a lookup table where the Roman numerals are mapped to their corresponding integer values.

We initialize an empty string `roman` to store the resulting Roman numeral.

We then iterate through the lookup table in descending order, starting from the largest symbol. While the given number `num` is greater than or equal to the current symbol's value, we subtract that value from `num` and append the corresponding symbol to the `roman` string. We repeat this process until `num` becomes zero.

Finally, we return the resulting `roman` string.

Here's an example usage of the `intToRoman` function:

``````console.log(intToRoman(27)); // Output: "XXVII"
console.log(intToRoman(4)); // Output: "IV"
console.log(intToRoman(58)); // Output: "LVIII"``````

The time complexity of this algorithm is O(1) because the maximum number of iterations in the for loop is constant, regardless of the input size.

The space complexity is also O(1) because we use a constant amount of extra space regardless of the input size.