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.
1public class Solution {
2 public String intToRoman(int num) {
3 int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
4 String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
5
6 StringBuilder sb = new StringBuilder();
7
8 for (int i = 0; i < values.length; i++) {
9 while (num >= values[i]) {
10 sb.append(symbols[i]);
11 num -= values[i];
12 }
13 }
14
15 return sb.toString();
16 }
17
18 public static void main(String[] args) {
19 Solution solution = new Solution();
20 int number = 1994;
21 System.out.println("Roman numeral for " + number + " is " + solution.intToRoman(number));
22 }
23}Java's implementation utilizes a StringBuilder for efficient string concatenation. It iterates through an array of numeral values, building the Roman numeral until the entire number converts.