DEV Community

Ayowande Oluwatosin
Ayowande Oluwatosin

Posted on • Edited on

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')
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)

nextjs tutorial video

Youtube Tutorial Series 📺

So you built a Next.js app, but you need a clear view of the entire operation flow to be able to identify performance bottlenecks before you launch. But how do you get started? Get the essentials on tracing for Next.js from @nikolovlazar in this video series 👀

Watch the Youtube series

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay