Integer to Roman Solution In C++/Java/Python/Javascript
Problem Description
We are given the task to convert an integer to its equivalent Roman numeral representation. Roman numerals use a specific set of symbols that correspond to certain values. The seven symbols used are I, V, X, L, C, D, and M. Here's their corresponding values: I represents 1
V represents 5
X represents 10
L represents 50
C represents 100
D represents 500
M represents 1000
Roman numerals are written by combining these symbols starting from the largest to the smallest from left to right.
“Given an integer, convert it to a Roman numeral.”
Examples:
Input: num = 3749
Output: MMMDCCXLIX
Explanation: 3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
700 = DCC as 500 (D) + 100 (C) + 100 (C)
40 = XL as 10 (X) less of 50 (L)
9= IX as 1 (I) less of 10 (X)
Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places
Input: num=58
Output: “LVIII”
Explanation: 50 for L and VIII for 8
Constraints:
1<= num <=3999
Approach 1
When we read the problem statement, the first idea that comes to mind is simple:
We use the largest Roman numeral symbols first and then move to smaller ones, appending symbols to our result string as we go. At every step, we reduce the number by the value of the Roman numeral we added.
For example:
If the number is 3749:
- Start with M=1000 and see how many MMM's fit in 3749.
- Subtract 3000 (3 MMM's) from 3749, leaving 749.
- Move to the next smaller numeral, D=500D = 500D=500, and repeat.
- Continue this process until the number is reduced to 0
This ensures the Roman numeral representation is constructed in descending order of value.
How to do it:
Define a list of Roman numeral symbols and their values in descending order: [M: 1000, D: 500, C:100,L:50,X:10,V:5,I:1]
Iterate Through the Values:
Start with the largest Roman numeral value (M=1000) and walk down to the smallest (I=1).
For each numeral, check if the numeral’s value can fit into the remaining number. Example: If the number is 3749:
- Start with M=1000 : 3749 ≥ 1000, so M fits.
Add Symbols to the Result:
Append the Roman numeral to the result string whenever its value fits into the number.
Subtract the numeral's value from the number to account for the conversion.
Example: 3749:
- Add "M" to the result and subtract 1000. Remaining number: 2749.
- Add another "M" and subtract 1000. Remaining number: 1749.
- Add another "M" and subtract 1000. Remaining number: 749.
Continue Until the Number is Fully Converted:
Repeat the process for all symbols until the entire number is reduced to zero.
Ensure subtractive combinations are handled correctly by their placement in the list.
Return the Roman Numeral:
- Once the entire number has been converted, return the accumulated string representing the Roman numeral.
integer-to-roman-Brute Force Animation Explaination
Let's walk through an example:
Dry run for Input: num = “3749”
- Start with num = 3749, result = "".
- Check against 1000 (M):
- Append M thrice (3000 fits into 3749).
- result = "MMM", num = 749.
- Check 900 (CM):
- Does not fit. Move to the next value.
- Check 500 (D):
- Append D once (500 fits into 749).
- result = "MMMD", num = 249.
- Check 100 (C):
- Append C twice (200 fits into 249).
- result = "MMMDCC", num = 49.
- Check 50 (L):
- Does not fit. Move to the next value.
- Check 40 (XL):
- Append XL once (40 fits into 49).
- result = "MMMDCCXL", num = 9.
- Check 10 (X):
- Does not fit. Move to the next value.
- Check 9 (IX):
- Append IX once (9 fits into 9).
- result = "MMMDCCXLIX", num = 0.
Output: "MMMDCCXLIX"
How to code it up:
- Initialize the Result String:
- Start by defining an empty string ans that will store the resulting Roman numeral.
- Iterate While num is Non-Zero:
- Use a while loop to process the integer num until it becomes zero.
- Check for Largest Roman Numeral Representations:
- Use conditional checks (e.g., if-else if) to match the current value of num to the largest Roman numeral representation it can accommodate:
- For example, check if num >= 1000 to append "M" and subtract 1000 from num.
- Handle Subtractive Cases:
- Include conditions for special cases like 900 (CM), 400 (CD), 90 (XC), 40 (XL), 9 (IX), and 4 (IV).
- Append the corresponding Roman numeral and subtract the appropriate value from num.
- Reduce num Gradually:
- For standard Roman numerals like M, C, X, or I, keep appending the symbol to ans and decrement num by the respective value.
- Return the Result:
- After processing all cases and reducing num to zero, return the constructed ans string.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
string intToRoman(int num) {
//Initialize the ans string
string ans = "";
//calculate the roman numbers
while (num) {
if (num >= 1000) {
ans += "M";
num -= 1000;
}
//check for all the corner cases like 900,400,90,40,9,4 etc.
else if (num >= 900 && num < 1000) {
ans += "CM";
num -= 900;
}
else if (num >= 500 && num < 900) {
ans += "D";
num -= 500;
}
else if (num >= 400 && num < 500) {
ans += "CD";
num -= 400;
}
else if (num >= 100 && num < 400) {
ans += "C";
num -= 100;
}
else if (num >= 90 && num < 100) {
ans += "XC";
num -= 90;
}
else if (num >= 50 && num < 90) {
ans += "L";
num -= 50;
}
else if (num >= 40 && num < 50) {
ans += "XL";
num -= 40;
}
else if (num >= 10 && num < 40) {
ans += "X";
num -= 10;
}
else if (num == 9) {
ans += "IX";
num -= 9;
}
else if (num >= 5 && num < 9) {
ans += "V";
num -= 5;
}
else if (num == 4) {
ans += "IV";
num -= 4;
}
else if (num < 4) {
ans += "I";
num--;
}
}
//return the result
return ans;
}
};2. Java Try on Compiler
class Solution {
public String intToRoman(int num) {
// Initialize the ans string
String ans = "";
// calculate the roman numbers
while (num > 0) {
if (num >= 1000) {
ans += "M";
num -= 1000;
}
// check for all the corner cases like 900,400,90,40,9,4 etc.
else if (num >= 900 && num < 1000) {
ans += "CM";
num -= 900;
} else if (num >= 500 && num < 900) {
ans += "D";
num -= 500;
} else if (num >= 400 && num < 500) {
ans += "CD";
num -= 400;
} else if (num >= 100 && num < 400) {
ans += "C";
num -= 100;
} else if (num >= 90 && num < 100) {
ans += "XC";
num -= 90;
} else if (num >= 50 && num < 90) {
ans += "L";
num -= 50;
} else if (num >= 40 && num < 50) {
ans += "XL";
num -= 40;
} else if (num >= 10 && num < 40) {
ans += "X";
num -= 10;
} else if (num == 9) {
ans += "IX";
num -= 9;
} else if (num >= 5 && num < 9) {
ans += "V";
num -= 5;
} else if (num == 4) {
ans += "IV";
num -= 4;
} else if (num < 4) {
ans += "I";
num--;
}
}
// return the result
return ans;
}
};3. Python Try on Compiler
class Solution(object):
def intToRoman(self, num):
ans = ""
# calculate the roman numbers
while num > 0:
if num >= 1000:
ans += "M"
num -= 1000
elif num >= 900:
ans += "CM"
num -= 900
elif num >= 500:
ans += "D"
num -= 500
elif num >= 400:
ans += "CD"
num -= 400
elif num >= 100:
ans += "C"
num -= 100
elif num >= 90:
ans += "XC"
num -= 90
elif num >= 50:
ans += "L"
num -= 50
elif num >= 40:
ans += "XL"
num -= 40
elif num >= 10:
ans += "X"
num -= 10
elif num == 9:
ans += "IX"
num -= 9
elif num >= 5:
ans += "V"
num -= 5
elif num == 4:
ans += "IV"
num -= 4
elif num < 4:
ans += "I"
num -= 1
# return the result
return ans
4. Javascript Try on Compiler
/**
* @param {number} num
* @return {string}
*/
var intToRoman = function(num) {
// Initialize the ans string
let ans = "";
// calculate the roman numbers
while(num != 0){
if(num >= 1000){
ans += "M";
num -= 1000;
}
//check for all the corner cases like 900,400,90,40,9,4 etc.
else if(num >= 900 && num < 1000){
ans += "CM";
num -= 900;
}
else if (num >= 500 && num < 900) {
ans += "D";
num -= 500;
}
else if (num >= 400 && num < 500) {
ans += "CD";
num -= 400;
}
else if (num >= 100 && num < 400) {
ans += "C";
num -= 100;
}
else if (num >= 90 && num < 100) {
ans += "XC";
num -= 90;
}
else if (num >= 50 && num < 90) {
ans += "L";
num -= 50;
}
else if (num >= 40 && num < 50) {
ans += "XL";
num -= 40;
}
else if (num >= 10 && num < 40) {
ans += "X";
num -= 10;
}
else if (num == 9) {
ans += "IX";
num -= 9;
}
else if (num >= 5 && num < 9) {
ans += "V";
num -= 5;
}
else if (num == 4) {
ans += "IV";
num -= 4;
}
else if (num < 4) {
ans += "I";
num--;
}
}
// return the result
return ans;
};
Time Complexity: O(k)
The time complexity is determined by the number of iterations in the while loop, which depends on the value of num.
- Number of Iterations:
The while loop runs until num becomes 0.
Each iteration appends one Roman numeral symbol to the result string ans and reduces num by the corresponding value.
The number of iterations is directly proportional to the number of symbols in the Roman numeral representation of num.
For example:
- num = 1987 translates to Roman MCMLXXXVII (9 symbols).
- Iterations: The loop subtracts 1000(M),900(CM),50(L),10(X),10(X),10(X),5(V),1(I),1(I), resulting in 9 iterations.
2.Length of Roman Numeral Representation:
- For any integer, the number of symbols in its Roman numeral representation is proportional to its magnitude, as Roman numerals are constructed digit by digit.Example:
- num=58: Roman numeral = LVIII → 4 symbols → 4 iterations.
- num=1987: Roman numeral = MCMLXXXVII → 9 symbols → 9 iterations.
Thus, the loop runs O(k) iterations, where k is the length of the Roman numeral representation.
3.Checking Conditions:
- Each iteration involves up to 13 conditional checks (corresponding to 13 numeral-value pairs).
- These checks are constant in number and independent of num.
4.String Operations:
- Appending a symbol to ans takes O(1) on average, due to efficient string operations in modern programming languages.
Final Time Complexity:
- O(k) where k is the number of symbols in the Roman numeral representation of num.
Space Complexity: O(n)
Auxiliary Space Complexity: O(1)
Explanation: The algorithm does not use any additional data structures such as arrays or maps.The space used for variables like ans and num is O(1).
Total Space Complexity: O(n)
Explanation: The space used for the output string (ans) grows proportionally to the size of the Roman numeral representation.
The maximum length of the Roman numeral for an integer num is proportional to n where n is the length of the output.
Will Approach 1 Work Within the Given Constraints?
Let’s analyze the problem with respect to the given constraints:
In approach 1, we iterate through a fixed set of Roman numeral values (13 in total) and repeatedly subtract the largest possible value from num, appending the corresponding Roman numeral to the result string. The number of iterations is proportional to the value of num, as each iteration reduces the number by a substantial amount depending on the Roman numeral used.
For the maximum input value of 3999, the algorithm would make a total of approximately 15 iterations, corresponding to the 15 characters in the Roman numeral representation of 3999 ("MMMCMXCIX"). Even for the upper limit, the brute force method involves fewer than 20 operations, which is well within the capabilities of modern computational environments. Additionally, the string concatenation operations are efficient, given the small size of the output string.
Therefore, the above approach comfortably handles the given constraints without exceeding space limitations.
Approach 2
In Approach 1 to converting integers to Roman numerals, we repeatedly subtract the largest possible Roman numeral value from the input number, appending the corresponding symbol to the result string. This process involves checking conditions multiple times for each Roman numeral value, which can make it less efficient.
In this approach we convert an integer to its Roman numeral representation using a vector of pairs to store Roman numeral values and their corresponding symbols. The algorithm iterates through this vector, starting with the largest numeral value. For each numeral, it repeatedly subtracts the numeral's value from the input integer and appends its symbol to the result string until the input integer is reduced to zero. This ensures the Roman numeral representation is constructed in descending order of value.
How to Do It:
- Store Roman Numerals: Create a vector of pairs containing Roman numeral values and their symbols in descending order, starting from M(1000) to I(1).
- Iterate Through the Values:Use a loop to traverse the vector of numeral-value pairs.
- Build the Roman Numeral:For each numeral, use a while loop to check if the current numeral’s value can fit into the remaining number. If it can, append the symbol to the result string and subtract the value from the number.
- Repeat Until Zero:Continue this process until the input number is fully reduced to zero.
- Return the Result:After constructing the Roman numeral, return the result string.
Let's walk through an example:
Input: num=1987
Steps:
- Initialize Roman as an empty string.Vector: {(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")}.
- Iterate through the vector:
- 1987≥1000: Append M, subtract 1000 → 987. Roman="M".
- 987≥900: Append CM, subtract 900 → 87.Roman="MCM".
- 87≥50: Append L, subtract 50 → 37.Roman="MCML".
- 37≥10: Append X, subtract 10 → 27.Roman="MCMLX".
- 27≥10: Append X, subtract 10 → 17.Roman="MCMLXX".
- 17≥10: Append X, subtract 10 → 7.Roman="MCMLXXX".
- 7≥5: Append V, subtract 5 → 2.Roman="MCMLXXXV".
- 2≥1: Append I, subtract 1 → 1.Roman="MCMLXXXVI".
- 1≥1: Append I, subtract 1 →0.Roman="MCMLXXXVII".
Output:
Roman="MCMLXXXVII"
How to code it up:
1. Define the Mapping:
Use a list of pairs to store Roman numeral values and their corresponding symbols.Arrange the pairs in descending order of values so that larger values are prioritized during the conversion.
2. Iterate and Construct the Result:
Start with the largest value in the mapping.
Use a loop to check how many times the current value fits into the input number (num).Append the corresponding Roman numeral symbol to the result string each time the value fits.Subtract the value from num to update the remaining number.
3.Continue Until Zero:
Move to the next smaller value in the mapping after completing the checks for the current value.Repeat the process until num becomes zero. This ensures that the Roman numeral is constructed in descending order of values.
Code Implementation
1. C++ Try on Compiler
Class Solution {
public:
string intToRoman(int num) {
// Step 1: Define the mapping
vector<pair<int, string>> storeIntRoman = {
{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"}
};
// Step 2: Initialize result string
string Roman = "";
// Step 3: Iterate and construct result
for (auto &entry : storeIntRoman) {
while (num >= entry.first) {
Roman += entry.second; // Append Roman numeral
num -= entry.first; // Reduce the number
}
}
// Step 4: Return final Roman numeral
return Roman;
}
};2. Java Try on Compiler
class Solution {
public String intToRoman(int num) {
// Step 1: Define the mapping
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
// Step 2: Initialize result string
StringBuilder Roman = new StringBuilder();
// Step 3: Iterate and construct result
for (int i = 0; i < values.length; i++) {
while (num >= values[i]) {
Roman.append(symbols[i]); // Append Roman numeral
num -= values[i]; // Reduce the number
}
}
// Step 4: Return final Roman numeral
return Roman.toString();
}
};3. Python Try on Compiler
class Solution(object):
def intToRoman(self, num):
# Step 1: Define the mapping
storeIntRoman = [
(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")
]
# Step 2: Initialize result string
Roman = ""
# Step 3: Iterate and construct result
for value, symbol in storeIntRoman:
while num >= value:
Roman += symbol # Append Roman numeral
num -= value # Reduce the number
# Step 4: Return final Roman numeral
return Roman4. Javascript Try on Compiler
/**
* @param {number} num
* @return {string}
*/
var intToRoman = function(num) {
// Step 1: Define the mapping
const storeIntRoman = [
[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"]
];
// Step 2: Initialize result string
let Roman = "";
// Step 3: Iterate and construct result
for (const [value, symbol] of storeIntRoman) {
while (num >= value) {
Roman += symbol; // Append Roman numeral
num -= value; // Reduce the number
}
}
// Step 4: Return final Roman numeral
return Roman;
};
Time Complexity: O(k)
Let’s break down the time complexity:
1.Outer Loop:
The storeIntRoman array contains 13 entries (for Roman numeral values).The outer for loop iterates through all 13 entries, which is a constant number of iterations: O(13) → O(1).
2.Inner Loop:
For each key in the mapping, the while loop repeatedly subtracts the key's value from num and appends the corresponding symbol to the result string.
The number of iterations of the inner while loop depends on the value of num and the Roman numeral representation.
Each Roman numeral symbol in the final result corresponds to one iteration of the while loop. Hence, the total number of iterations across all keys is proportional to the number of Roman numeral symbols in the output string.
Overall Time Complexity:
- The total number of iterations is bounded by the number of symbols in the Roman numeral representation, which depends on the input value num.
- The time complexity is O(k), where k is the length of the Roman numeral representation of num.
Space Complexity: O(k)
Auxiliary Space Complexity: O(1)
Explanation: The storeIntRoman vector occupies a fixed amount of space since it contains 13 key-value pairs.This is O(1).Variables like Roman, num occupy constant space: O(1).
Total Space Complexity: O(k)Explanation:
1.The vector storeIntRoman, which stores Roman numeral values and their corresponding symbols, is a fixed-sized data structure containing 13 key-value pairs. Regardless of the input number, this map occupies constant space, contributing O(1) to the space complexity.
2.The result string (Roman) grows dynamically as symbols are appended based on the input number.The space required is proportional to the length of the Roman numeral representation of the input number, contributing O(k) to the space complexity, where k is the length of the output string.
The overall space complexity is dominated by the result string, making the total space complexity O(k), where k is the length of the Roman numeral representation of the num.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.
Since the result may be very large, so you need to return a string instead of an integer.
You are given two strings order and s. All the characters of order are unique and were sorted in some custom order previously.
Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.
Return any permutation of s that satisfies this property.