Solution For Integer To Roman
Problem description:
Given an integer, convert it to a roman numeral.
Example 1:
Input: num = 3
Output: “III”
Example 2:
Input: num = 4
Output: “IV”
Example 3:
Input: num = 9
Output: “IX”
Example 4:
Input: num = 58
Output: “LVIII”
Explanation: L = 50, V = 5, III = 3.
Example 5:
Input: num = 1994
Output: “MCMXCIV”
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Solution approach:
The problem can be solved using a greedy approach, where we keep subtracting the maximum possible value of a roman numeral from the given number and add its corresponding roman numeral to the result string until the number becomes 0.
To implement this approach, we can create a mapping of integers to their corresponding roman numerals. We can then iterate over the mapping in descending order and check if the current integer value is less than or equal to the given number. If it is, we add the corresponding roman numeral to the result string and subtract the integer value from the given number. We repeat this process until the given number becomes 0.
Solution in Python:
class Solution:
def intToRoman(self, num: int) -> str:
# Mapping of integers to their corresponding roman numerals
mapping = {
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’
}
# Result string
result = ''
# Iterate over the mapping in descending order
for integer, roman in mapping.items():
# Check if the current integer value is less than or equal to the given number
while num >= integer:
# Add the corresponding roman numeral to the result string and subtract the integer value from the given number
result += roman
num -= integer
# Return the result string
return result
This solution has a time complexity of O(1), as we are iterating over a fixed number of integers, and a space complexity of O(1), as we are only using a fixed number of variables.
Step by Step Implementation For Integer To Roman
/**
* @author:
* @date:
* @description:
*/
class Solution {
public String intToRoman(int num) {
// create a StringBuilder to store the resulting Roman numeral
StringBuilder roman = new StringBuilder();
// create an array of Roman numeral characters
String[] romanChars = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
// create an array of decimal values corresponding to the Roman numeral characters
int[] decimalValues = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
// loop through the decimal values array
for (int i = 0; i < decimalValues.length; i++) {
// while the decimal value at the current index is less than or equal to the input num
while (decimalValues[i] <= num) {
// append the Roman numeral character at the current index to the StringBuilder
roman.append(romanChars[i]);
// subtract the decimal value at the current index from the input num
num -= decimalValues[i];
}
}
// return the resulting Roman numeral stored in the StringBuilder
return roman.toString();
}
}class Solution:
def intToRoman(self, num: int) -> str:
# create a list of tuples where each tuple consists of
# a roman numeral and its corresponding integer value
roman_numerals = [
('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)
]
# initialize an empty string to store the roman numeral
roman_numeral = ''
# loop through the list of tuples
for roman, integer in roman_numerals:
# while the input number is greater than or equal to
# the integer value of the current roman numeral
while num >= integer:
# add the roman numeral to the string
roman_numeral += roman
# subtract the integer value of the roman numeral
# from the input number
num -= integer
# return the string containing the roman numeral
return roman_numeralvar intToRoman = function(num) {
// create an empty string to store the roman numeral
var roman = "";
// create an array of all the decimal values that correspond to a roman numeral
var decimalValue = [ 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 ];
// create an array of all the roman numerals
var romanNumeral = [ "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" ];
// loop through the decimal values array
for (var index = 0; index < decimalValue.length; index++) {
// while the decimal value at the current index is less than or equal to the number passed into the function
while (decimalValue[index] <= num) {
// add the roman numeral at the current index to our roman numeral string
roman += romanNumeral[index];
// subtract the decimal value at the current index from the number passed into the function
num -= decimalValue[index];
}
}
// return the completed roman numeral string
return roman;
};class Solution {
public:
string intToRoman(int num) {
// create a map of all roman numerals and their integer values
unordered_map roman_map = {
{1, "I"},
{4, "IV"},
{5, "V"},
{9, "IX"},
{10, "X"},
{40, "XL"},
{50, "L"},
{90, "XC"},
{100, "C"},
{400, "CD"},
{500, "D"},
{900, "CM"},
{1000, "M"}
};
// create a vector of all the integer values in the map
vector values;
for (auto i : roman_map) {
values.push_back(i.first);
}
// sort the vector in reverse order
sort(values.rbegin(), values.rend());
// initialize an empty string to store the roman numeral
string roman = "";
// for each value in the vector,
// check if it is less than or equal to the input number
// if it is, add the corresponding roman numeral to the string
// and subtract the value from the input number
for (int i : values) {
while (num >= i) {
roman += roman_map[i];
num -= i;
}
}
return roman;
}
}; public class Solution {
public string IntToRoman(int num) {
// Create a string array with all of the Roman numerals.
// We'll use this array to lookup the numerals as we
// build up the final string.
string[] numerals = new string[] { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
// Create an array with all of the corresponding values.
// We'll use this array to determine which Roman numeral
// to use for each value we need to output.
int[] values = new int[] { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
// This will be the string we build up that will eventually
// contain the final Roman numeral representation of `num`.
string romanNumeral = "";
// Loop through the `values` array, starting at the largest
// value and working our way down to 1.
for (int i = 0; i < values.Length; i++) {
// As long as `num` is greater than or equal to the
// current value in the `values` array, we can keep
// "consuming" that value by outputting the Roman numeral
// and subtracting the value from `num`.
while (num >= values[i]) {
romanNumeral += numerals[i];
num -= values[i];
}
}
return romanNumeral;
}
}