How to convert integers to numerals

Question

The following code only converts the integers to numerals up to 1010. At that point, an error starts to occur.

class Solution:
    def intToRoman(self, num: int) -> str:
        numerals = {
            1: "I", 
            4: "IV", 
            5: "V", 
            10: "X",
            40: "XL",
            50: "L", 
            90: "XC",
            100: "C", 
            400: "CD",
            500: "D", 
            900: "CM",
            1000: "M"
        }
        
        output = ""

        for k,v in sorted(numerals.items(), reverse=True):
            while num >= k:
                output += v
                num -= k
        
        return output

I am looping through the numerals dictionary from greatest to least number wise and getting the ints (v) and the numerals (k)

Then I am using a while loop to see if the number is >= value (v)

After that output will be added to the numerals (k), and number (num) will be subtracted from the integer (v).

Then I return value.

I was thinking of doing something like an if statement maybe like:

if num < v:
   # code

Whenever I try adding that, I get a "Time Limit Exceeded"

Why are you defining a numeral to int mapping if the goal is to do the opposite? this seems like the wrong way to go about it to me. — rv.kvetch, Oct 21 '21 at 22:08
There are errors way before you get to 1010. Try 10 (X), 40 (XL), and 80 (LXXX). — Woodford, Oct 21 '21 at 22:09
@Woodford any ways to help fix the code? I am trying to stick with what I have now, but then add something to make it correct. — Jake, Oct 21 '21 at 22:13
You have `"X": 100,` instead of `"C": 100,` and `'V': 50` instead of `'L': 50`, and you're missing "XL", "CD", and "CM". When I run your code with 2345, it certainly prints good info. — Tim Roberts, Oct 21 '21 at 22:14
My mistake, that SO post I linked was actually asking the exact opposite, apparently. — rv.kvetch, Oct 21 '21 at 22:16
Also you're depending on the order of the items in the dict. [You can't always rely on that](https://stackoverflow.com/questions/5629023/the-order-of-keys-in-dictionaries) — Woodford, Oct 21 '21 at 22:19
You never really use the dictionary **as a dictionary**. You could just as easily use a list of tuples if order was really needed to be consistent — OneCricketeer, Oct 21 '21 at 22:24
As @TimRoberts suggested, you have a few incorrect mappings. For ex. `50: "V"`, but that should be `50: "L"`. Also add the edge case mappings as pointed out like for 9, 40, etc. and you should be in business; that will fix it so roman numerals like 9 and 19 are properly handled by your code, for example. — rv.kvetch, Oct 21 '21 at 22:34
@Woodford It's safe to rely on the order of dictionary items, in [Python 3.7 and onwards](https://stackoverflow.com/a/39980744/1431750). — aneroid, Oct 21 '21 at 23:05
@TimRoberts my mistake. I was honestly very careless. I fixed now, am updating the code as we speak. — Jake, Oct 22 '21 at 00:03
@Woodford I changed it to `sorted(numerals.items(), reverse=True)` would that help? — Jake, Oct 22 '21 at 00:03

Tim Roberts · Answer 1 · 2021-10-21T22:25:40.557

2

I'm not sure what you're seeing. When I fix your typos, this code produces good results.

However, in the interest of micro-optimization, I've replaced your unnecessary dictionary with a tuple that is already in order:

class Solution:
    numerals = (
        ("M", 1000),
        ("CM", 900),
        ("D", 500), 
        ("CD", 400), 
        ("C", 100), 
        ("XC", 90),
        ("L", 50), 
        ("XL", 40), 
        ("X", 10), 
        ("IX", 9),
        ("V", 5), 
        ("IV", 4), 
        ("I", 1), 
    )
        
    def intToRoman(self, num: int) -> str:
        output = ""

        for k,v in self.numerals:
            while num >= v:
                output += k 
                num -= v
        
        return output

s = Solution()
print( s.intToRoman( 10 ) )
print( s.intToRoman( 19 ) )
print( s.intToRoman( 4345 ) )

edited Oct 21 '21 at 22:25

answered Oct 21 '21 at 22:19

Tim Roberts

48,973
4
21
30

It may run, yes, but when submitted to HackerRank, for example, OP gets time limit exceeded – OneCricketeer Oct 21 '21 at 22:21
1

That's not what he said. He only said "an error starts to occur". He only mentioned the time limit with his final change. You may be right, but the post didn't say that. – Tim Roberts Oct 21 '21 at 22:23
1

One other optimization - change output to a list, then use `return ''.join(output)`. – OneCricketeer Oct 21 '21 at 22:30

score 2 · Answer 2 · answered Oct 22 '21 at 00:09

I have optimized the code with all the suggestions posted on this. The following works with runtime coming in at 61 ms and memory usage of 14.2 MB.

You can use Tim Roberts method too (marked correct above)

Or you can use the following code:

My original method w/ added code and fixed options

class Solution:
    def intToRoman(self, num: int) -> str:
        numerals = {
            1: "I", 
            4: "IV", 
            5: "V",
            9: "IX",
            10: "X",
            40: "XL",
            50: "L", 
            90: "XC",
            100: "C", 
            400: "CD",
            500: "D", 
            900: "CM",
            1000: "M"
        }
        
        output = ""

        for k,v in sorted(numerals.items(), reverse=True):
            while num >= k:
                output += v
                num -= k
        
        return output

I appreciate everyone's help!

How to convert integers to numerals

2 Answers2