EasyMath

Roman to Integer

Q: Why cast s.size() to int before subtracting 1?

size() returns an unsigned size_t, so on an empty string s.size() - 1 wraps to a huge number and i >= 0 is always true for an unsigned i. Casting first, (int)s.size() - 1, gives -1 and the loop never starts.

Q: Why values.at(ch) instead of values[ch]?

On a const map operator[] does not compile, because it inserts a default 0 for a missing key. at works on a const map and throws std::out_of_range when the key is absent, which turns a bad letter into a clear failure instead of a silent 0.

Q: Why does the replace helper continue from pos + to.size()?

Searching again from pos would look inside the text just inserted. That is harmless for these pairs, but for a rewrite like "A" to "AA" it never terminates. Skipping past the replacement is the safe default for any find-and-replace loop.

Q: Is a lookup table faster than the switch?

A static const int table[128] indexed by the character is one load per letter; the switch is a few comparisons or a jump table. Either is far below a microsecond for 15 letters. The switch keeps the values readable and handles every other byte in its default branch.

You get a string s holding a Roman numeral written in uppercase letters. Return its value as an integer. The seven letters are worth I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 and M = 1000.

Letters are written from largest to smallest and their values add up: CCLXII is 100 + 100 + 50 + 10 + 1 + 1 = 262. Six pairs break that order and subtract instead: a smaller letter placed directly before a larger one is taken away from it. They are IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 and CM = 900.

The input is always a well-formed numeral in standard form for a value from 1 to 3999, so you never have to reject an invalid string.

Examples

Input

s = "XLVII"

Output47WhyXL is the subtractive pair for 40, then V adds 5 and II adds 2: 40 + 5 + 2 = 47.

Input

s = "MCDLXXIX"

Output1479WhyM is 1000, CD is 400, LXX is 70 and IX is 9: 1000 + 400 + 70 + 9 = 1479.

Constraints

Size: 1 ≤ s.length ≤ 15
Characters: s holds only I V X L C D M
Values: 1 ≤ value ≤ 3,999
Answer: The input is always a valid numeral in standard form.
Time limit: 10 s per run, all cases

Run your code 2 more times to open the solutions. The idea sticks better after an attempt.

2 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.

1 · Rewrite the six subtractive pairs, then add letter values

O(n) time · O(n) space

String.replace swaps every occurrence of a literal, so six calls rewrite each subtractive pair in its additive spelling, such as IX to VIIII. The resulting string only adds, and a loop over toCharArray() sums the values from an immutable Map.of.

import java.util.*;

public class Main {
    static final Map<Character, Integer> VALUES =
        Map.of('I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000);

    static int romanToInt(String s) {
        s = s.replace("IV", "IIII").replace("IX", "VIIII")
             .replace("XL", "XXXX").replace("XC", "LXXXX")
             .replace("CD", "CCCC").replace("CM", "DCCCC");
        int total = 0;
        for (char ch : s.toCharArray()) {
            total += VALUES.get(ch);
        }
        return total;
    }
}

2 · One right-to-left pass with a value map

O(n) time · O(1) space

recommended

Walk from the last character to the first with charAt, keeping the value of the letter to the right in prev. A letter worth less than prev opens a subtractive pair and is subtracted; every other letter is added. The letter values come from a switch expression on the primitive char, so nothing is boxed and no new string is built.

import java.util.*;

public class Main {
    static int value(char c) {
        return switch (c) {
            case 'I' -> 1;
            case 'V' -> 5;
            case 'X' -> 10;
            case 'L' -> 50;
            case 'C' -> 100;
            case 'D' -> 500;
            case 'M' -> 1000;
            default -> throw new IllegalArgumentException("not a Roman letter: " + c);
        };
    }

    static int romanToInt(String s) {
        int total = 0;
        int prev = 0; // value of the letter to the right
        for (int i = s.length() - 1; i >= 0; i--) {
            int v = value(s.charAt(i));
            total += v < prev ? -v : v;
            prev = v;
        }
        return total;
    }
}

2 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.

1 · Rewrite the six subtractive pairs, then add letter values

O(n) time · O(n) space

Six chained Replace calls rewrite each subtractive pair additively (XL to XXXX, CD to CCCC), and a foreach over the result sums the letter values from a Dictionary<char, int>.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    static readonly Dictionary<char, int> Values = new()
    {
        ['I'] = 1, ['V'] = 5, ['X'] = 10, ['L'] = 50, ['C'] = 100, ['D'] = 500, ['M'] = 1000,
    };

    public static int RomanToInt(string s)
    {
        s = s.Replace("IV", "IIII").Replace("IX", "VIIII")
             .Replace("XL", "XXXX").Replace("XC", "LXXXX")
             .Replace("CD", "CCCC").Replace("CM", "DCCCC");
        int total = 0;
        foreach (char ch in s) total += Values[ch];
        return total;
    }
}

2 · One right-to-left pass with a value map

O(n) time · O(1) space

recommended

Walk from the last character to the first, keeping the value of the letter to the right in prev. A letter worth less than prev opens a subtractive pair and is subtracted; every other letter is added. A switch expression maps each char to its value without a dictionary or a new string.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    static int Value(char c) => c switch
    {
        'I' => 1,
        'V' => 5,
        'X' => 10,
        'L' => 50,
        'C' => 100,
        'D' => 500,
        'M' => 1000,
        _ => throw new ArgumentException($"not a Roman letter: {c}"),
    };

    public static int RomanToInt(string s)
    {
        int total = 0;
        int prev = 0; // value of the letter to the right
        for (int i = s.Length - 1; i >= 0; i--)
        {
            int v = Value(s[i]);
            total += v < prev ? -v : v;
            prev = v;
        }
        return total;
    }
}

2 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.

1 · Rewrite the six subtractive pairs, then add letter values

O(n) time · O(n) space

The standard library has no replace-all for strings, so a small helper loops find and replace until the pattern is gone. Six calls rewrite the subtractive pairs additively (IX to VIIII, CM to DCCCC), and an unordered_map<char, int> sums what is left. s arrives by value, so rewriting it touches only our own copy.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int romanToInt(string s) {
        static const unordered_map<char, int> values = {
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000},
        };
        static const vector<pair<string, string>> spelled = {
            {"IV", "IIII"}, {"IX", "VIIII"}, {"XL", "XXXX"}, {"XC", "LXXXX"}, {"CD", "CCCC"}, {"CM", "DCCCC"},
        };
        for (const auto& [from, to] : spelled) replaceAll(s, from, to);
        int total = 0;
        for (char ch : s) total += values.at(ch);
        return total;
    }

private:
    static void replaceAll(string& s, const string& from, const string& to) {
        for (size_t pos = s.find(from); pos != string::npos; pos = s.find(from, pos + to.size())) {
            s.replace(pos, from.size(), to);
        }
    }
};

2 · One right-to-left pass with a value map

O(n) time · O(1) space

recommended

Walk from the last character to the first, keeping the value of the letter to the right in prev. A letter worth less than prev opens a subtractive pair and is subtracted; every other letter is added. A switch maps each char to its value, so there is no hashing and no allocation.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int romanToInt(string s) {
        int total = 0;
        int prev = 0; // value of the letter to the right
        for (int i = (int)s.size() - 1; i >= 0; i--) {
            int v = value(s[i]);
            total += v < prev ? -v : v;
            prev = v;
        }
        return total;
    }

private:
    static int value(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;
        }
    }
};

2 reference approaches in C, from brute force to the one to reach for. Compare them with yours.

1 · Rewrite the six subtractive pairs, then add letter values

O(n) time · O(n) space

C has no string replace, so do the rewrite in one scan: copy s into a malloc'ed buffer, and wherever the next two characters form a subtractive pair, write its additive spelling instead (CM becomes DCCCC). The longest spelling is five letters for two, so 5 * len / 2 + 1 bytes always fit. Then sum the buffer letter by letter and free it before returning.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static int value(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;
    }
}

static const char* spelled(char a, char b) {
    if (a == 'I' && b == 'V') return "IIII";
    if (a == 'I' && b == 'X') return "VIIII";
    if (a == 'X' && b == 'L') return "XXXX";
    if (a == 'X' && b == 'C') return "LXXXX";
    if (a == 'C' && b == 'D') return "CCCC";
    if (a == 'C' && b == 'M') return "DCCCC";
    return NULL;
}

int romanToInt(char* s) {
    size_t len = strlen(s);
    char* buf = malloc(5 * len / 2 + 1);
    size_t n = 0;
    for (size_t i = 0; i < len; i++) {
        const char* pair = i + 1 < len ? spelled(s[i], s[i + 1]) : NULL;
        if (pair) {
            size_t k = strlen(pair);
            memcpy(buf + n, pair, k);
            n += k;
            i++; // both letters of the pair are consumed
        } else {
            buf[n++] = s[i];
        }
    }
    int total = 0;
    for (size_t i = 0; i < n; i++) total += value(buf[i]);
    free(buf);
    return total;
}

2 · One right-to-left pass with a value map

O(n) time · O(1) space

recommended

Walk from the last character back to the first, keeping the value of the letter to the right in prev. A letter worth less than prev opens a subtractive pair and is subtracted; every other letter is added. A switch on the char gives the values, so the function allocates nothing and reads s exactly once.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static int value(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(char* s) {
    int total = 0;
    int prev = 0; // value of the letter to the right
    for (size_t i = strlen(s); i-- > 0;) {
        int v = value(s[i]);
        total += v < prev ? -v : v;
        prev = v;
    }
    return total;
}

2 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.

1 · Rewrite the six subtractive pairs, then add letter values

O(n) time · O(n) space

Each subtractive pair has an additive spelling: IV is IIII, CM is DCCCC. Folding the six pairs over the string with str::replace returns a new String of letters that only add, and bytes().map(value).sum() adds them up.

impl Solution {
    fn value(b: u8) -> i32 {
        match b {
            b'I' => 1,
            b'V' => 5,
            b'X' => 10,
            b'L' => 50,
            b'C' => 100,
            b'D' => 500,
            b'M' => 1000,
            _ => panic!("not a Roman letter: {}", b as char),
        }
    }

    pub fn roman_to_int(s: String) -> i32 {
        const PAIRS: [(&str, &str); 6] = [
            ("IV", "IIII"), ("IX", "VIIII"), ("XL", "XXXX"),
            ("XC", "LXXXX"), ("CD", "CCCC"), ("CM", "DCCCC"),
        ];
        let additive = PAIRS.iter().fold(s, |acc, (pair, spelled)| acc.replace(pair, spelled));
        additive.bytes().map(Self::value).sum()
    }
}

2 · One right-to-left pass with a value map

O(n) time · O(1) space

recommended

Iterate s.bytes().rev(), keeping the value of the letter to the right in prev. A letter worth less than prev opens a subtractive pair and is subtracted; every other letter is added. Roman numerals are ASCII, so bytes are safe and cheaper than chars(), and nothing is allocated.

impl Solution {
    fn value(b: u8) -> i32 {
        match b {
            b'I' => 1,
            b'V' => 5,
            b'X' => 10,
            b'L' => 50,
            b'C' => 100,
            b'D' => 500,
            b'M' => 1000,
            _ => panic!("not a Roman letter: {}", b as char),
        }
    }

    pub fn roman_to_int(s: String) -> i32 {
        let mut total = 0;
        let mut prev = 0; // value of the letter to the right
        for b in s.bytes().rev() {
            let v = Self::value(b);
            if v < prev {
                total -= v;
            } else {
                total += v;
            }
            prev = v;
        }
        total
    }
}

FAQ for C++

Why cast s.size() to int before subtracting 1?

size() returns an unsigned size_t, so on an empty string s.size() - 1 wraps to a huge number and i >= 0 is always true for an unsigned i. Casting first, (int)s.size() - 1, gives -1 and the loop never starts.

Why values.at(ch) instead of values[ch]?

On a const map operator[] does not compile, because it inserts a default 0 for a missing key. at works on a const map and throws std::out_of_range when the key is absent, which turns a bad letter into a clear failure instead of a silent 0.

Why does the replace helper continue from pos + to.size()?

Searching again from pos would look inside the text just inserted. That is harmless for these pairs, but for a rewrite like "A" to "AA" it never terminates. Skipping past the replacement is the safe default for any find-and-replace loop.

Is a lookup table faster than the switch?

A static const int table[128] indexed by the character is one load per letter; the switch is a few comparisons or a jump table. Either is far below a microsecond for 15 letters. The switch keeps the values readable and handles every other byte in its default branch.

Should I include bits/stdc++.h to save typing?

It compiles on GCC but pulls in the whole standard library, which adds a couple of seconds to every Run here. This problem needs only <string>, plus <unordered_map> and <vector> for the rewrite version.

Keep going

Majority Element15 / 40 · Arrays · Easy

roman_to_int.cpp

C++ 15.3

Not run yet

+ 7 hidden

Input

s = "XLVII"

Expected

XL is the subtractive pair for 40, then V adds 5 and II adds 2: 40 + 5 + 2 = 47.