In this article, we will walk you through Integer to Roman in Java problem and what can be done to achieve faster results.
1. The Problem
Given an integer number, we must return a String that represents the given number in Roman numerals. With some exceptions, Roman numerals are usually written from the largest (left) to the smallest (right) and we say usually because if we take the number 4, for instance, in Roman numerals we write IV which means 5 – 1 = 4.
Here are all symbols in our application: I, V, X, L, C, D & M, and their respective values: 1, 5, 10, 50, 100, 500 & 1000.
I
can be placed beforeV
(5) andX
(10) to make 4 and 9.X
can be placed beforeL
(50) andC
(100) to make 40 and 90.C
can be placed beforeD
(500) andM
(1000) to make 400 and 900.
2. Solving Integer to Roman in Java By Using Regular Structured Code
Our first impulse is to add a loop and a lot of validations, one for each of the numbers from the largest to the smallest, and, as soon as we eliminate the thousands, there can be no thousands anymore, then the nine-hundreds, five-hundreds, so on and so forth.
public static String intToRomanHardWay(int num) { StringBuilder toRoman = new StringBuilder(); if (num <= 0) return toRoman.toString(); while (num >= 1000) { toRoman.append("M"); num -= 1000; } if (num >= 900) { toRoman.append("CM"); num -= 900; } else { if (num >= 500) { toRoman.append("D"); num -= 500; } else if (num >= 400) { toRoman.append("CD"); num -= 400; } while (num >= 100) { toRoman.append("C"); num -= 100; } } if (num >= 90) { toRoman.append("XC"); num -= 90; } else { if (num >= 50) { toRoman.append("L"); num -= 50; } else if (num >= 40) { toRoman.append("XL"); num -= 40; } while (num >= 10) { toRoman.append("X"); num -= 10; } } if (num == 9) { toRoman.append("IX"); } else { if (num >= 5) { toRoman.append("V"); num -= 5; } else if (num >= 4) { toRoman.append("IV"); num -= 4; } while (num-- > 0) toRoman.append("I"); } return toRoman.toString(); }
Here are the results of our solution, just to make sure our solution works properly and has consistent results; we submitted it three times.
Notice how memory consumption behaves for this solution. It seems that after the submission, we tend to get worse results.
As you can see, our runtime is very consistent while memory consumption varies a bit. However, the biggest issue here is how long and hard to read this function is. Indeed, it is not complicated code, but it is far from elegant or maintainable, which leads us to our second solution using dynamic programming.
3. Solving Integer to Roman in Java by Using Dynamic Programming
One of the most significant improvements Dynamic Programming brings to the table is optimization, especially on high-demanding algorithms. It caches reusable calculations to be used later without having to process them all over again. That being said, this challenge at hand is a demanding one, so we won’t see the optimization benefit of it. However, it will bring readability and it will make our method a lot shorter.
static final String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; static final int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }; public static String intToRoman(int num) { StringBuilder intToRoman = new StringBuilder(); int index = 0; while (num > 0) { if (num / values[index] > 0) { intToRoman.append(romans[index]); num -= values[index]; continue; // So it won't change the index unless if fails } index++; } return intToRoman.toString(); }
Undeniably, the code above looks so much more professional and cleaner as we were able to reduce the size of the method significantly.
The reasoning behind this solution is that we have a finite number of options and values that we can choose from, so why not cache it? Besides, by making it final and static we help the compiler optimize the code statically which may result in faster executions and less memory consumption.
3.1 Method Explanation
We have two arrays of the same size where the largest number starts at position zero, consequently the String
that represents it in Roman "M" does as well. We will also need an index
variable to control what position of the array we are in. Finally, we check whether num
divided by the value in that index results in a number greater than zero, which means that num
is greater than values[index]
.
For example, let’s say we pass 900 to our method and our array is at index 0, which is 1000. If we divide 900 / 1000 we get 0.9. However, since we are dealing with integers, this number is truncated and everything after.
will be discarded. In this specific case, our if
fails and we increase the index to 1. Now our loop starts over and we have num / values[index]
, which translates to 900 / 900 = 1. Finally, we append the String
in romans[index]
, that is, "CM", deduce the value from num
, and use continue
to restart the loop since there can be more than one for the following numbers: 1000, 100, 10, 1.
Here are the results:
For this solution, memory consuption behaves the opposite, that is, it tends to get better as we submit more times.
As you can see, by the third submission we achieved outstanding results even for memory consumption.
4. Conclusion
By now you should be able to solve this problem using a more structured approach as well as using dynamic programming, which makes for far code even when there is no real gain in performance. You can find the source code on our GitHub Page.