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 <stdio.h>
2#include <string.h>
3
4char* intToRoman(int num) {
5 static char result[20];
6 result[0] = '\0';
7 int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
8 char* symbols[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
9
10 for (int i = 0; i < 13; ++i) {
11 while (num >= values[i]) {
12 strcat(result, symbols[i]);
13 num -= values[i];
14 }
15 }
16
17 return result;
18}
19
20int main() {
21 int number = 1994;
22 printf("Roman numeral for %d is %s\n", number, intToRoman(number));
23 return 0;
24}The C implementation defines an array of integer values and corresponding Roman symbols. A loop iterates through these values, subtracting the largest possible from the input number, and appends the associated Roman symbol to the result string.