CoderByte Question

......the question was something like this.......

Question: write a function that takes a string argument. The numerals used are I for 1, V for 5, X for 10, I for 50, C for 100, D for 500, M for 1000. Given IIIXXXVVVV is 200. Should return CC.

Solution:

function rommanToIntAndBack($s){
    $numerals = [
        'M' => 1000,'D' => 500,'C' => 100, 'L' => 50, 'X' => 10, 'V' => 5,'I' => 1, 
    ];

    $total = 0;

    for ($i = 0; $i < strlen($s); $i++) {
        $total += $numerals[$s[$i]];
    }

    $roman = '';
    foreach($numerals as $key => $val){
        while ($total >= $val) {
            $total -= $val;
            $roman .= $key;
        }
    }
    return $roman;
}
rommanToIntAndBack('IIIXXXVVVV')

Explanation:

Associative Array (HashMap):

• The $numerals array is an associative array that maps Roman numeral characters to their corresponding integer values.
• This array provides constant time complexity 𝑂(1) for lookups, which is efficient for converting characters to their integer values.

Algorithm Analysis

Part 1: Roman to Integer Conversion

Algorithm:

1. Initialize $total to 0.
2. Iterate through each character in the string $s:
3. Look up the integer value of the character from the $numerals array.
4. add the current value to $total.

Time Complexity:
The conversion from Roman to integer involves a single pass through the string, so the time complexity is O(n), where n is the length of the string.

Space Complexity:
The space complexity is O(1) as no additional space proportional to the input size is used (only a few variables are used).

Part 2: Integer to Roman Conversion

Algorithm:

1. Initialize an empty string $roman.
2. Iterate through the $numerals array:
3. For each numeral, while the integer value can be subtracted from $total, subtract it and append the numeral character to $roman.

Time Complexity:
The conversion from integer to Roman numerals involves iterating through a fixed set of numeral values and repeatedly subtracting them from $total.
In the worst case, the time complexity can be considered O(n), where
n is the value of the integer. However, given the fixed number of Roman numeral symbols, it is more practical to consider it as O(1).

Space Complexity:
The space complexity is O(1) for the numerical operations and O(n) for the output string, where n is the length of the resulting Roman numeral string.