# How to improve code?

• I know the easy way of solving this problem is using 23 case statements (10 for numbers [1-10], 10 for [10-100], 10 for [1000-3000]). But the code does not look good and it's getting bit long. I'm thinking even applying the rules for converting may also make the code complex. Any suggestions?

• I think the following rule works

1. If num is 4 times of `x` (`x = 1000, 100, 10, 1`), add `x 5x`
2. If num is greater than `x`, add `x`
3. If num is smaller than `x` (`x = 1000, 100, 10, 1`) but it is 9 times of `x/10`, add `10/x x`

``````class Solution {
public:
string intToRoman(int num) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
string result = "";
int base[] = {1000,500,100,50,10,5,1,0};
char baseC[] = {'M','D','C','L','X','V','I'};
int basen = 0;
while(num) {
if(basen%2 == 0 && num/base[basen] == 4) {
result += baseC[basen];
result += baseC[basen-1];
num -= base[basen] * 4;
} else if(num >= base[basen]) {
result += baseC[basen];
num -= base[basen];
} else if(basen%2 == 0 && num / base[basen+2] == 9) {
result += baseC[basen+2];
result += baseC[basen];
num -= base[basen+2]*9;
} else {
basen++;
}
}
return result;
}
};``````

• cool algorithm!

• ``````import java.util.LinkedHashMap;
public class Solution {

static {
numToRoman.put(1000, "M");
numToRoman.put(900, "CM");
numToRoman.put(500, "D");
numToRoman.put(400, "CD");
numToRoman.put(100, "C");
numToRoman.put(90, "XC");
numToRoman.put(50, "L");
numToRoman.put(40, "XL");
numToRoman.put(10, "X");
numToRoman.put(9, "IX");
numToRoman.put(5, "V");
numToRoman.put(4, "IV");
numToRoman.put(1, "I");
}
public String intToRoman(int num) {
for (Integer i : numToRoman.keySet()) {
if (num >= i) {
return numToRoman.get(i) + intToRoman(num - i);
}
}
return "";
}
}``````

• Changing the method body to use StringBuilder and a while loop will be faster than recursion. But it does make the code a bit longer.

http://en.wikipedia.org/wiki/Roman_numerals

• ``````class Solution {
public:
string intToRoman(int num) {
string ret;
char d[] = "--MDCLXVI";
char *p = d, d1, d5, d10;
int a, b, base = 1000;
while(num){
d10 = *p++;
d5 = *p++;
d1 = *p;
a = num / base;
b = a % 5;
if(b < 4){
if(a >= 5) ret += d5;
for(int i = 0; i < b; ++i) ret += d1;
}else{
ret += d1;
if(a == 9){
ret += d10;
}else{
ret += d5;
}
}
num -= a * base;
base /= 10;
}
return ret;
}
};``````

• This code looks really neat, but it loops many times. Will it make the code slow?

• Yes, like I mentioned in the first reply. Changing from recursion to iteration actually helped me lower the run time from 844ms to 576ms (at the cost of four extra lines).

• ``````class Solution:
roman_dict = [
(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')
]
def intToRoman(self, num):
for kv in self.roman_dict:
if kv[0] <= num:
return kv[1] + self.intToRoman(num - kv[0])
return ''``````

• I divide it into 30 cases and list them explicitly. I notice people normally scan all the cases each time, but we actually can skip some when the number is decreased. So I add an variable "offset" to indicate where to start next scan.

``````class Solution:
decs = [3000, 2000, 1000]+range(900, 0, -100)+range(90, 0, -10)+range(9, 0, -1)
romans = ['MMM', 'MM', 'M',
'CM', 'DCCC', 'DCC', 'DC', 'D', 'CD', 'CCC', 'CC', 'C',
'XC', 'LXXX', 'LXX', 'LX', 'L', 'XL', 'XXX', 'XX', 'X',
'IX', 'VIII', 'VII', 'VI', 'V', 'IV', 'III', 'II', 'I']
offsets = [3]*3+[12]*9+[21]*9+[30]*9

# @return a string
def intToRoman(self, num):
roman = []
offset = 0
size = len(self.decs)
while num > 0:
for i in range(offset, size):
if num >= self.decs[i]:
roman.append(self.romans[i])
num -= self.decs[i]
offset = self.offsets[i]
break;
return ''.join(roman)``````

• This is just a C++ version translated from Java and Python solutions given by magicknife and others.

``````class Solution {
public:
string intToRoman(int num) {
for (int i = 0; i < int_dict.size(); i++) {
if (int_dict[i] <= num)
return roman_dict[i] + intToRoman(num - int_dict[i]);
}
return "";
}
private:
vector<int> int_dict {1000, 900, 500, 400, 100,
90, 50, 40, 10, 9, 5, 4, 1};
vector<string> roman_dict {"M", "CM", "D", "CD",
"C", "XC", "L", "XL", "X",
"IX", "V", "IV", "I"};
};``````

• Great! very cute

• ``````public class Solution {
public String intToRoman(int num) {
StringBuffer res=new StringBuffer();
while(num>0)
{
if(num-1000>=0)
{
res.append("M");
num-=1000;
}
else if(num-900>=0)
{
res.append("CM");
num-=900;
}
else if(num-500>=0)
{
res.append("D");
num-=500;
}
else if(num-400>=0)
{
res.append("CD");
num-=400;
}
else if(num-100>=0)
{
res.append("C");
num-=100;
}
else if(num-90>=0)
{
res.append("XC");
num-=90;
}
else if(num-50>=0)
{
res.append("L");
num-=50;
}
else if(num-40>=0)
{
res.append("XL");
num-=40;
}
else if(num-10>=0)
{
res.append("X");
num-=10;
}
else if(num-9>=0)
{
res.append("IX");
num-=9;
}
else if(num-5>=0)
{
res.append("V");
num-=5;
}
else if(num-4>=0)
{
res.append("IV");
num-=4;
}
else if(num-1>=0)
{
res.append("I");
num-=1;
}
}
return res.toString();
}
``````

}

This code can avoid use extra memory space .But since there are many if judgement , I don't know this code 's time complexity.Any body have any ideas?

• `if` doesn't effect time complexity. In terms of time complexity, it usually counts on loops and recursions. For this particular problem, I don't think time complexity would be a problem at all.

• ``````class Solution {
public:
string intToRoman(int num) {
string res;
int temp = num;
int val[] = {1000, 500, 100, 50, 10, 5, 1};
char sym[] = {'M', 'D', 'C', 'L', 'X','V', 'I'};

for (int i = 0; i < sizeof(sym)/sizeof(char); i+=2)
{
int count = temp / val[i];
if (count < 4)
res.append(count, sym[i]);
else if (count == 4)
{
res.append(1, sym[i]);
res.append(1, sym[i-1]);
}
else if (count > 4 && count < 9)
{
res.append(1, sym[i-1]);
res.append(count - 5, sym[i]);
}
else if (count == 9)
{
res.append(1, sym[i]);
res.append(1, sym[i-2]);
}
temp = temp % val[i];
}

return res;
}
};``````

• This is my code, I think it's concise enough.

``````public class Solution {
public String intToRoman(int num) {
if(num>=1000) return "M"+intToRoman(num-1000);
if(num>=900) return "CM"+intToRoman(num-900);
if(num>=500) return "D"+intToRoman(num-500);
if(num>=400) return "CD"+intToRoman(num-400);
if(num>=100) return "C"+intToRoman(num-100);
if(num>=90) return "XC"+intToRoman(num-90);
if(num>=50) return "L"+intToRoman(num-50);
if(num>=40) return "XL"+intToRoman(num-40);
if(num>=10) return "X"+intToRoman(num-10);
if(num>=9) return "IX"+intToRoman(num-9);
if(num>=5) return "V"+intToRoman(num-5);
if(num>=4) return "IV"+intToRoman(num-4);
if(num>=1) return "I"+intToRoman(num-1);
return "";
}
}``````

• This post is deleted!

• This post is deleted!

• Is it ok if I put roman_dict inside of intToRoman function and change the first line of the function to "for kv in roman_dict:"? Thanks!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.