roman to integer leetcode in C fails for MCMXCIV

Question

The last test case of s = "MCMXCIV" is not working. the output is 3099 instead of 1994. I have added all the roman numerals to integers and can't figure out where the issue is. The first two cases were properly executed to give expected output.

// code start
int romanToInt(char *s) {
    int sum = 0;
    if (*s == NULL) {
        return NULL;
    }
    for (int i = 0; i < strlen(s); i++) {
        if (s[i] == 'M') {
            sum = sum + 1000;
        }
        if (s[i] == 'D') {
            sum = sum + 500;
        }
        if (s[i] == 'C') {
            sum = sum + 100;
        }
        if (s[i] == 'L') {
            sum = sum + 50;
        }
        if (s[i] == 'X') {
            sum = sum + 10;
        }
        if (s[i] == 'V') {
            sum = sum + 5;
        }
        if (s[i] == 'I') {
            sum = sum + 1;
        }
        if (i > 0) {
            if (s[i] == 'V' && s[i - 1] == 'I') {
                sum = sum + 3;
            }
            if (s[i] == 'X' && s[i - 1] == 'I') {
                sum = sum + 8;
            }
            if (s[i] == 'L' && s[i - 1] == 'X') {
                sum = sum + 30;
            }
            if (s[i] == 'C' && s[i - 1] == 'X') {
                sum = sum + 80;
            }
            if (s[i] == 'D' && s[i - 1] == 'C') {
                sum = sum + 300;
            }
            if (s[i] == 'M' && s[i - 1] == 'C') {
                sum = sum + 800;
            }
        }
        //sum represents the converted integer
    }
    return sum;
}//code end

Answer 1

There are multiple problems:

• comparing *s to NULL is incorrect: NULL is a macro representing a null pointer, *s is not a pointer, it is a character, which you can compare to '\0' or 0 instead. Your code compiles by chance if NULL is defined as 0 or 0L but would not for the alternative classic definition ((void *)0).

• this initial test is useless anyway as the for loop will stop immediately for an empty string.

• the test i < strlen(s) may recompute the string length at each iteration, which is inefficient. You could just test if s[i] != '\0'.

• the rule for roman numerals is simple: if a letter value is less than that of the next letter, its value is subtracted from the value of the next one.

Here is a modified version:

int romanDigit(char c) {
    switch (c) {
      case 'I': return 1;
      case 'V': return 5;
      case 'X': return 10;
      case 'L': return 50;
      case 'C': return 100;
      case 'D': return 500;
      case 'M': return 1000;
      default: return 0;
    }
}

int romanToInt(const char *s) {
    int sum = 0;
    while (*s) {
        int digit = romanDigit(*s++);
        int next = romanDigit(*s);
        if (digit && digit < next) {
            sum += next - digit;
            s++;
        } else {
            sum += digit;
        }
    }
    return sum;
}

This simplistic implementation works for MCMXCIV (1994) but does not detect invalid numbers such as MXMIV, MVMI, XMMIV... which will be all produce 1994 as well. The classic representations only use I, X and C in front of the next 2 letters, but many variations have been found throughout the long history of Roman Numerals.

Roman numerals embody one of the most durable human inventions of all time: counting. The shape of the letters I, V and X look amazingly similar to Tally marks found on prehistoric artifacts. It gives me the chills to see in the most scientifically advanced publications the very shapes used by stone age cavemen to count.

Answer 2

Your basic approach is solid, but your conditions are not in the proper order, and you likely want to use else to ensure only one branch can execute. As characters are integral, you can use a switch statement.

You can then check if you're on the first character and continue to skip control flow over the remainder of the loop where you check the preceding character and go straight to the next iteration.

for (int i = 0; i < strlen(s); i++) {
    switch (s[i]) {
        case 'M':
        sum += 1000;
        break;

        case 'D':
        sum += 500;
        break;

        case 'C':
        sum += 100;
        break;
 
        case 'L': 
        sum += 50;
        break;
       
        case 'X':
        sum += 10;
        break;
     
        case 'V':
        sum += 5;
        break;
  
        case 'I':
        sum += 1;
        break; 
    }

    if (i == 0) continue;

    if (s[i] == 'M' && s[i-1] == 'C') 
        sum -= 100;
    else if (s[i] == 'V' && s[i-1] == 'I')
        sum -= 1;
    // and so on...
}

Answer 3

Here is a fairly simple program to do it. Note that it does not check for invalid strings. But it has a much cleaner design and separates the actual roman values from the logic of calculating them.

It utilizes these rules:

• Repeating numbers adds to each other
• A smaller number followed by a bigger means subtraction
• When any of above is done, calculate the result and add with the rest

It does NOT follow these rules

• D, L and V cannot be repeated
• No letter can be repeated more than 3 times
• Subtractable letters are I, X or C
• Subtraction must be made with the largest subtractable letter

And possibly a few other rules that I did not implement.

Code:

#include <stdio.h>

int val(char c) {
    switch(c) {
    case 'M': return 1000;
    case 'D': return 500;
    case 'C': return 100;
    case 'L': return 50;
    case 'X': return 10;
    case 'V': return 5;
    case 'I': return 1; 
    default: return 0; // To make base case work
    }   
}

int roman(char *s) {
    char cur = *s;

    // Base case
    if(cur == 0) return 0;

    // Subtraction like IX
    char next = s[1];
    int diff = val(next) - val(cur);
    if(diff > 0) return diff + roman(&s[2]);

    // This takes care of repeating numbers, or just continues
    return val(cur) + roman(&s[1]);;
}
 
void printRoman(char *s) {
    printf("%s = %d\n", s, roman(s));
}
 
int main(void) {
    printRoman("M");
    printRoman("MM");
    printRoman("MMM");
    printRoman("MMMCM");
    printRoman("IV");
    printRoman("MCMXCIV");
}

Output:

M = 1000
MM = 2000
MMM = 3000
MMMCM = 3900
IV = 4
MCMXCIV = 1994

https://onlinegdb.com/poJLQy70C

Answer 4

Following the OP method of using a cascade of if() statements, there's the following. (Notice the absence of unnecessary curly braces, and the use of C's comma operator.) This makes use of C's 'pairing' an else with the "last else-less if".

#include <stdio.h>

int romanToInt( char *s ) {
    int sum = 0;

    for( size_t i = 0; s[i]; i++ ) {
        char d = s[i], n = s[i+1]; // this 'd'igit and the 'n'ext...
        int v = 0;

             if( d == 'M' )     v = 1000;
        else if( d == 'D' )     v = 500;
        else if( d == 'C' )
                 if( n == 'M' ) v = 900, i++; // "CM" is two chars meaning 900
            else if( n == 'D' ) v = 400, i++; // ... and so on.
            else                v = 100;
        else if( d == 'L' )     v = 50;
        else if( d == 'X' )
                 if( n == 'C' ) v = 90, i++;
            else if( n == 'L' ) v = 40, i++;
            else                v = 10;
        else if( d == 'V' )     v = 5;
        else if( d == 'I' )
                 if( n == 'X' ) v = 9, i++;
            else if( n == 'V' ) v = 4, i++;
            else                v = 1;

        sum += v;
    }
    return sum;
}

int main( void ) {
    char *test[] = { "MCMXCIV", "MMXXIII", "MCDXCII" };

    for( size_t i = 0; i < sizeof test/sizeof test[0]; i++ )
        printf( "%d: %s - %d\n", i, test[i], romanToInt( test[i] ) );

    return 0;
}

0: MCMXCIV - 1994
1: MMXXIII - 2023
2: MCDXCII - 1492

No effort has been made to ensure the source string is a valid Roman Numeral.

---

EDIT:
On the other hand, interweaving data and processing can lead to headaches.

For a conversion like this, a well thought out lookup table storing the mappings can be served by a tiny bit of code (such as the following.)

int romanToInt( char *ps ) {
    struct { int v; char *s; } rnc[] = {
        { 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"  },
    }, *p = rnc;

    int val = 0;

    while( *ps )
        if( ( p->s[0] == ps[0] ) && ( p->s[1] == '\0' || p->s[1] == ps[1] ) )
            val += p->v, ps += 1 + (p->s[1] != '\0');
        else
            p++;

    return val;
}

---

EDIT2:
A curly brace aficionado appears to dislike this answer.

In response, here is the previous version modified to check and reject invalid Roman Numerals... Easy maintenance when the design is already sound:

int romanToInt( char *ps ) {
    struct { int v; char *s; int skip; } rnc[] = {
        { 1000, "M", 0 }, {  900, "CM", 4 }, {  500, "D", 2  }, {  400, "CD", 2 },
        {  100, "C", 0 }, {   90, "XC", 4 }, {   50, "L", 2  }, {   40, "XL", 2 },
        {   10, "X", 0 }, {    9, "IX", 4 }, {    5, "V", 2  }, {    4, "IV", 2 },
        {    1, "I", 0  },
    }, *p = rnc;

    int val = 0, cnt = 0;

    while( *ps && val >= 0 && p < sizeof rnc/sizeof rnc[0] )
        if( ( p->s[0] == ps[0] ) && ( p->s[1] == '\0' || p->s[1] == ps[1] ) )
            if( ++cnt > (p-skip ? 1 : 3) ) // Disallow some multiples
                val = -1;
            else
                val += p->v, // add the value
                ps += 1 + (p->s[1] != '\0'), // skip 1 or 2 chars of input
                p += p->skip, // advance to next(?) allowable substring
                cnt = p->skip ? 0 : cnt; // reset counter (if needed)
        else
            if( ++p > rnc + 12 )
                val = -1;
            else
                cnt = 0;

    return val;
}

int main( void ) {
    char *test[] = {
        "MCMXCIV", "MMXXIII", "MCDXCII", // all good
        "MCDCDXCII", "MCDXCCCCII", // both bad
        "III", "IIII" // good and bad
    };

    for( size_t i = 0; i < sizeof test/sizeof test[0]; i++ )
        printf( "%15s ==> %4d\n", test[i], romanToInt( test[i] ) );

    return 0;
}

Output:

        MCMXCIV ==> 1994
        MMXXIII ==> 2023
        MCDXCII ==> 1492
      MCDCDXCII ==>   -1
     MCDXCCCCII ==>   -1
            III ==>    3
           IIII ==>   -1