Roman numerals, a numeral system originating in ancient Rome, are still widely used today, especially in clocks, book chapters, and movie credits. While these numerals are fascinating, they can present a unique challenge when it comes to conversion between Roman and integer formats in programming. In this article, we will discuss how to efficiently implement Roman to Integer and Integer to Roman conversions in Kotlin, using simple and optimized solutions.
Introduction
In many programming tasks, you may need to convert Roman numerals to integers or vice versa. These conversions can often involve a significant amount of logic, as Roman numerals follow a distinct set of rules, including both additive and subtractive notations. The key is to design efficient algorithms that respect these rules while minimizing computational overhead.
Let’s dive into two important operations:
- Roman to Integer: Converting a Roman numeral (like
IV or MCMXCIV) to an integer (like 4 or 1994).
- Integer to Roman: Converting an integer (like
1994) back to a Roman numeral (like MCMXCIV).
Roman to Integer Conversion
Roman numerals are built on seven symbols:
I (1), V (5), X (10), L (50), C (100), D (500), and M (1000).
The Roman numeral system uses additive and subtractive notation. In additive notation, numerals are simply added together (e.g., VI = 5 + 1 = 6). However, in subtractive notation, a smaller numeral before a larger numeral indicates subtraction (e.g., IV = 5 - 1 = 4).
Approach
To convert a Roman numeral string to an integer efficiently, we:
- Traverse the string from right to left.
- Compare each numeral’s value with the numeral before it (i.e., the next numeral in the string from right to left).
- If the current numeral is smaller than the previous one, we subtract its value (indicating a subtractive combination). Otherwise, we add its value.
Solution Code
fun romanToInt(s: String): Int {
val romanMap = mapOf(
'I' to 1, 'V' to 5, 'X' to 10, 'L' to 50, 'C' to 100,
'D' to 500, 'M' to 1000
)
var result = 0
var prevValue = 0
for (char in s.reversed()) {
val currentValue = romanMap[char] ?: 0
if (currentValue < prevValue) {
result -= currentValue
} else {
result += currentValue
}
prevValue = currentValue
}
return result
}
Explanation of the Code
-
Mapping Roman Characters to Values: We use a map (romanMap) to associate each Roman numeral character with its corresponding integer value.
-
Reversing the String: We iterate through the Roman numeral string in reverse (from right to left) to make it easier to handle subtractive notation.
-
Addition or Subtraction: For each character, if its value is less than the value of the character processed earlier, we subtract it (for subtractive cases like IV or IX). Otherwise, we add it.
-
Final Result: After processing the entire string, the result contains the corresponding integer value.
Time Complexity
- O(n): We only iterate through the string once (where
n is the length of the Roman numeral), and the map lookup is O(1) for each character.
Integer to Roman Conversion
To convert an integer to a Roman numeral, the process is somewhat the reverse of the Roman to Integer conversion. Instead of subtracting values, we greedily subtract the largest possible Roman numeral values from the number and append their symbols to a string.
Approach
To convert an integer to a Roman numeral:
- Start with the largest possible Roman numeral (1000) and work down to the smallest (1).
- For each Roman numeral, subtract it from the number as many times as it fits, appending the corresponding symbol each time.
- Continue this process until the number becomes zero.
Solution Code
fun intToRoman(num: Int): String {
val values = intArrayOf(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)
val symbols = arrayOf("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I")
var number = num
val roman = StringBuilder()
for (i in values.indices) {
while (number >= values[i]) {
roman.append(symbols[i])
number -= values[i]
}
}
return roman.toString()
}
Explanation of the Code
-
Roman Values and Symbols: We define two arrays: values (the integer values of Roman numerals) and symbols (the corresponding Roman symbols).
-
Greedy Algorithm: For each value in the values array, we subtract the value from the integer (num) as many times as possible, appending the corresponding symbol to the result each time.
-
Build the Result: As we continue subtracting the largest possible Roman values, the StringBuilder (roman) is appended with the corresponding symbols until the number is reduced to zero.
-
Return Result: The final Roman numeral is returned as a string.
Time Complexity
- O(1): Since the Roman numeral system only has 13 distinct values, the loop runs a fixed number of times (13 iterations), making the time complexity constant, irrespective of the input size.
Example Usage
fun main() {
// Roman to Integer Conversion
val roman = "MCMXCIV"
println("Roman to Integer: $roman -> ${romanToInt(roman)}") // Output: 1994
// Integer to Roman Conversion
val number = 1994
println("Integer to Roman: $number -> ${intToRoman(number)}") // Output: MCMXCIV
}
Example Explanation
- Roman to Integer: The Roman numeral
MCMXCIV is converted to 1994 by using the rules of Roman numeral subtraction and addition.
- Integer to Roman: The integer
1994 is converted back to MCMXCIV by repeatedly subtracting the largest Roman numeral values.
Conclusion
Roman numeral conversion problems are often seen in interviews and coding challenges. By understanding the rules of Roman numerals—additive and subtractive notation—you can build efficient solutions for both Roman to Integer and Integer to Roman conversions.
- Roman to Integer: A simple right-to-left traversal of the string ensures we correctly handle both addition and subtraction rules.
- Integer to Roman: A greedy approach ensures that we subtract the largest Roman numeral values as many times as needed, creating an efficient solution.
Both of these solutions are O(n) for Roman to Integer and O(1) for Integer to Roman, making them highly efficient for most practical use cases. Whether you are coding for fun or preparing for a technical interview, mastering these conversions will add to your toolkit of problem-solving techniques in Kotlin.
Posts
