algoadvance

Leetcode 12. Integer to Roman

Problem Statement

Given an integer, convert it to a Roman numeral.

Clarifying Questions

  1. Range of Integer:
    • What is the range of the integer?
    • Response: The integer is between 1 and 3999 inclusive as traditionally accepted Roman numerals cover this range.
  2. Expected Output:
    • Is the output expected to be in uppercase Roman numerals?
    • Response: Yes, the traditional Roman numerals are typically represented in uppercase.

Strategy

To convert an integer to a Roman numeral, we should understand the Roman numeral system. Here are the basic symbols:

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

Special cases are when a smaller numeral appears before a larger numeral to indicate subtraction:

We can use a list of these values in descending order to form a greedy algorithm that repeatedly subtracts the largest possible value and appends the corresponding numeral to the result.

Code

Here is a C++ implementation for converting an integer to a Roman numeral:

#include <iostream>
#include <vector>
#include <string>

std::string intToRoman(int num) {
    // Define mappings of Roman symbols to their corresponding values
    std::vector<std::pair<int, std::string>> valueSymbols = {
        {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
        {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
        {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}
    };
    
    std::string result = "";
    
    // Iterate over the value-symbol pairs
    for (const auto &pair : valueSymbols) {
        // While we can subtract the current value from num, append the symbol
        while (num >= pair.first) {
            num -= pair.first;
            result += pair.second;
        }
    }
    
    return result;
}

int main() {
    int num = 1994;
    std::string roman = intToRoman(num);
    std::cout << "The Roman numeral for " << num << " is " << roman << std::endl;
    return 0;
}

Time Complexity

The time complexity of this approach is (O(1)). This is because:

  1. The number of operations is bounded by the number of Roman value-symbol pairs (which is always constant, specifically 13 pairs).
  2. The algorithm walks through the list of value-symbol pairs and subtracts these values from the input number.

Therefore, our algorithm runs in constant time with respect to the size of the input integer.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI