Sponsored
Sponsored
This approach utilizes a greedy strategy by iterating over an ordered list of numeral values and corresponding symbols. Starting from the largest value, it repeatedly subtracts from the given number until the result is less, appending the equivalent symbol each time. This ensures the numeral is created with the fewest characters.
Time Complexity: O(1) — The solution has a fixed iteration through a constant list of length 13, hence it's O(1).
Space Complexity: O(1) — Uses constant space for the result string and numeral arrays.
1def int_to_roman(num):
2 values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
3 symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
4 result = ""
5
6 for i in range(len(values)):
7 while num >= values[i]:
8 result += symbols[i]
9 num -= values[i]
10
11 return result
12
13number = 1994
14print(f"Roman numeral for {number} is {int_to_roman(number)}")By iterating over lists of integers and matching Roman numerals, the Python solution builds the numeral string by appending as long as the number remains equal or greater than the value being checked.