leetcode Question 36: Integer to Roman


Integer to Roman
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.


Analysis:
There is no standard way of transferring integer to Roman, this problem may have multiple ways.
Here is one solution but may not pass all the test.

Source Code:

class Solution {
public:
    string intToRoman(int num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
        int n_M = int(num/1000);
        num = num%1000;
        int n_D = int(num/500);
        num = num%500;
        int n_C = int(num/100);
        num = num%100;
        int n_L = int(num/50);
        num = num%50;
        int n_X = int(num/10);
        num = num%10;
        int n_V = int(num/5);
        num = num%5;
        int n_I = int(num/1);
        
        return string(n_M,'M')+string(n_D,'D')+string(n_C,'C')+string(n_L,'L')+string(n_X,'X')+string(n_V,'V')+string(n_I,'I');
        
    }
};


This code is another way of represent integer to roman, and this one can pass all the test:
According to the rule (from wiki):

  • A number written in Arabic numerals can be broken into digits. For example, 1903 is composed of 1 (one thousand), 9 (nine hundreds), 0 (zero tens), and 3 (three units). To write the Roman numeral, each of the non-zero digits should be treated separately. In the above example, 1,000 = M, 900 = CM, and 3 = III. Therefore, 1903 = MCMIII.[4]
  • The symbols "I", "X", "C", and "M" can be repeated three times in succession, but no more. (They may appear more than three times if they appear non-sequentially, such as XXXIX.) "D", "L", and "V" can never be repeated.[5][6]
  • "I" can be subtracted from "V" and "X" only. "X" can be subtracted from "L" and "C" only. "C" can be subtracted from "D" and "M" only. "V", "L", and "D" can never be subtracted[6]
  • Only one small-value symbol may be subtracted from any large-value symbol.[7]



class Solution {
public:
    string intToRoman(int num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
        string res;
        int n_M = int(num/1000);
        res += string(n_M,'M');
        num = num%1000;
        int n_C = int(num/100);
        if (n_C!=0){
        if (n_C<=3){res += string(n_C,'C');}
        if (n_C==4){res += "CD";}
        if (n_C>=5 && n_C<=8){ res+="D";res += string(n_C-5,'C');}
        if (n_C==9){res += "CM";}
        }
        num = num%100;
        int n_X = int(num/10);
        if (n_X!=0){
        if (n_X<=3){res += string(n_X,'X');}
        if (n_X==4){res += "XL";}
        if (n_X>=5 && n_X<=8){res+="L"; res += string(n_X-5,'X'); }
        if (n_X==9){res += "XC";}
        }
        num = num%10;
        int n_I = int(num/1);
        if (n_I!=0){
            if (n_I<=3){res += string(n_I,'I');}
            if (n_I==4){res += "IV";}
            if (n_I>=5 && n_I<=8){res+="V"; res += string(n_I-5,'I'); }
            if (n_I==9){res += "IX";}
        }
        return res;
    }
};

3 comments:

  1. public String intToRoman(int num) {
    int[] integer = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] roman = {"M", "CM", "D","CD","C", "XC","L","XL", "X", "IX","V","IV", "I"};

    if (num<1)
    return null;

    String str="";
    for(int i = 0; i < integer.length; i ++){
    int q = num/integer[i];
    while(q>0){
    str=str+roman[i];
    q--;
    }
    num=num%integer[i];
    }

    return str;
    }

    ReplyDelete
  2. def intToRoman(num):
    alph = "MDCLXVI"
    alphDict = { 'M':1000, 'D':500, 'C':100, 'L': 50,'X':10,'V':5,'I':1}
    numDict = { 1000:'M', 500:'D', 100:'C', 50:'L',10:'X',5:'V',1:'I'}
    result = ""

    while num > 0:
    for index,i in enumerate(alph):
    roman = alphDict[i]
    if num >= roman:
    pre = num / roman
    num = num % roman
    newNum = numDict[roman] * pre
    result += newNum
    for j in range(index+1,len(alph)):
    next = alphDict[alph[j]]
    if next * 2 != roman:
    if roman - next <= num < roman:
    result += numDict[next] + numDict[roman]
    num = num % (roman - next)
    return result

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete