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.
1#include <iostream>
2#include <vector>
3
4std::string intToRoman(int num) {
5 std::string result = "";
6 std::vector<int> values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
7 std::vector<std::string> symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
8
9 for (size_t i = 0; i < values.size(); ++i) {
10 while (num >= values[i]) {
11 result += symbols[i];
12 num -= values[i];
13 }
14 }
15
16 return result;
17}
18
19int main() {
20 int number = 1994;
21 std::cout << "Roman numeral for " << number << " is " << intToRoman(number) << std::endl;
22 return 0;
23}Utilizing a vector of integers and strings, the code iterates from the largest to smallest values, appending characters to a result string while decrementing the number. This ensures that the conversion covers all numeral types, including subtractive notation.