Roman to Integer Conversion in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Roman to Integer Conversion Function

What is the output of the following C++ code that converts a Roman numeral string to an integer?

DSA C++

int romanToInt(string s) {
    unordered_map<char, int> values{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
    int total = 0;
    for (int i = 0; i < s.size(); i++) {
        if (i + 1 < s.size() && values[s[i]] < values[s[i+1]]) {
            total -= values[s[i]];
        } else {
            total += values[s[i]];
        }
    }
    return total;
}

int main() {
    cout << romanToInt("MCMXCIV") << endl;
    return 0;
}

A 1094

B 1904

C 1994

D None (runtime error)

💡 Hint

Remember that when a smaller value precedes a larger one, you subtract it.

The Roman numeral MCMXCIV is 1000 + (1000-100) + (100-10) + (5-1) = 1994.

❓ Predict Output

intermediate

Result of Roman to Integer Conversion with Repeated Numerals

What is the output of this code when converting the Roman numeral "III" to an integer?

DSA C++

int romanToInt(string s) {
    unordered_map<char, int> values{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
    int total = 0;
    for (int i = 0; i < s.size(); i++) {
        if (i + 1 < s.size() && values[s[i]] < values[s[i+1]]) {
            total -= values[s[i]];
        } else {
            total += values[s[i]];
        }
    }
    return total;
}

int main() {
    cout << romanToInt("III") << endl;
    return 0;
}

A 2

B 4

C 0

D 3

💡 Hint

Repeated 'I's add up.

Each 'I' is 1, so three 'I's add up to 3.

❓ Predict Output

advanced

Output for Complex Roman Numeral with Subtractions

What is the output of this code when converting the Roman numeral "XLII" to an integer?

DSA C++

int romanToInt(string s) {
    unordered_map<char, int> values{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
    int total = 0;
    for (int i = 0; i < s.size(); i++) {
        if (i + 1 < s.size() && values[s[i]] < values[s[i+1]]) {
            total -= values[s[i]];
        } else {
            total += values[s[i]];
        }
    }
    return total;
}

int main() {
    cout << romanToInt("XLII") << endl;
    return 0;
}

A 40

B 42

C 52

D 48

💡 Hint

XL means 50 - 10.

XL is 40 (50 - 10), plus II is 2, total 42.

🧠 Conceptual

advanced

Why Subtraction is Needed in Roman to Integer Conversion

Why does the Roman to Integer conversion algorithm subtract the value of a numeral when it appears before a larger numeral?

A Because Roman numerals use subtraction to represent numbers like 4 (IV) and 9 (IX).

B Because the algorithm is designed to handle invalid Roman numerals.

C Because all Roman numerals are added regardless of order.

D Because subtraction is used only for numerals larger than 1000.

💡 Hint

Think about how Roman numerals represent numbers like 4 and 9.

Roman numerals place smaller values before larger ones to indicate subtraction, e.g., IV = 5 - 1 = 4.

❓ Predict Output

expert

Output of Roman to Integer Conversion for Large Numeral

What is the output of this code when converting the Roman numeral "MMMDCCCLXXXVIII" to an integer?

DSA C++

int romanToInt(string s) {
    unordered_map<char, int> values{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
    int total = 0;
    for (int i = 0; i < s.size(); i++) {
        if (i + 1 < s.size() && values[s[i]] < values[s[i+1]]) {
            total -= values[s[i]];
        } else {
            total += values[s[i]];
        }
    }
    return total;
}

int main() {
    cout << romanToInt("MMMDCCCLXXXVIII") << endl;
    return 0;
}

A 3888

B 3880

C 3889

D 3898

💡 Hint

Add all values since no smaller numeral precedes a larger one.

MMMDCCCLXXXVIII is 3000 + 800 + 80 + 8 = 3888.

Practice

1. What is the value of the Roman numeral IX when converted to an integer?

easy

A. 11

B. 6

C. 9

D. 19

Solution

1. Step 1: Understand Roman numeral rules for subtraction

   In Roman numerals, when a smaller numeral appears before a larger one, it is subtracted. Here, I (1) is before X (10), so subtract 1 from 10.

2. Step 2: Calculate the integer value

   10 - 1 = 9.

3. Final Answer:

   9 -> Option C

4. Quick Check:

   IX = 9 [OK]

Hint: Subtract when smaller numeral precedes larger one [OK]

Common Mistakes:

• Adding values instead of subtracting for IX
• Confusing IX with XI
• Ignoring subtraction rule

2. Which of the following C++ code snippets correctly initializes a map for Roman numeral values?

easy

A. std::map roman{{'I', 1}, {'V', 5}, {'X', 10}};

B. std::map roman = {'I':1, 'V':5, 'X':10};

C. std::map roman = {('I', 1), ('V', 5), ('X', 10)};

D. std::map roman = [('I', 1), ('V', 5), ('X', 10)];

Solution

1. Step 1: Check C++ map initialization syntax

   In modern C++, maps can be initialized using initializer lists with curly braces and pairs inside curly braces.

2. Step 2: Identify correct syntax

   std::map roman{{'I', 1}, {'V', 5}, {'X', 10}}; uses double braces with pairs correctly. Options A, B, and C use invalid syntax for map initialization.

3. Final Answer:

   std::map roman{{'I', 1}, {'V', 5}, {'X', 10}}; -> Option A

4. Quick Check:

   Correct map initialization syntax [OK]

Hint: Use double braces with pairs for map initialization [OK]

Common Mistakes:

• Using colon instead of comma in initializer list
• Using parentheses instead of braces for pairs
• Using square brackets for initialization

3. What is the output of the following C++ code snippet?

std::string s = "MCMXCIV";
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int result = 0;
for (int i = 0; i < s.size(); ++i) {
  if (i + 1 < s.size() && roman[s[i]] < roman[s[i+1]]) {
    result -= roman[s[i]];
  } else {
    result += roman[s[i]];
  }
}
std::cout << result << std::endl;

medium

A. 1904

B. 1994

C. 1094

D. 1949

Solution

1. Step 1: Trace the loop through the string "MCMXCIV"

   Check each character and compare with next: M(1000), C(100), M(1000), X(10), C(100), I(1), V(5). Subtract when current < next, else add.

2. Step 2: Calculate result step-by-step

   Positions: M(1000, add), C(100, next M=1000 > 100 subtract), M(1000, add), X(10, next C=100 > 10 subtract), C(100, add), I(1, next V=5 > 1 subtract), V(5, add). Calculation: 1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994.

3. Final Answer:

   1994 -> Option B

4. Quick Check:

   Roman "MCMXCIV" = 1994 [OK]

Hint: Subtract if current < next, else add [OK]

Common Mistakes:

• Adding all values without subtraction
• Misreading character values
• Off-by-one errors in loop

4. Identify the bug in the following C++ code for Roman to Integer conversion:

int romanToInt(std::string s) {
  std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
  int result = 0;
  for (int i = 0; i < s.size(); ++i) {
    if (roman[s[i]] < roman[s[i+1]]) {
      result -= roman[s[i]];
    } else {
      result += roman[s[i]];
    }
  }
  return result;
}

medium

A. Accessing s[i+1] without checking bounds causes out-of-range error

B. Using map instead of unordered_map causes slow lookup

C. Result variable should be initialized to 1 instead of 0

D. The subtraction logic is reversed

Solution

1. Step 1: Analyze loop and index usage

   The loop runs from i = 0 to s.size() - 1, but inside the loop it accesses s[i+1] without checking if i+1 is within bounds.

2. Step 2: Identify potential runtime error

   When i is the last index, s[i+1] is out of range, causing undefined behavior or crash.

3. Final Answer:

   Accessing s[i+1] without checking bounds causes out-of-range error -> Option A

4. Quick Check:

   Check index bounds before accessing s[i+1] [OK]

Hint: Always check index bounds before accessing next element [OK]

Common Mistakes:

• Ignoring index bounds causing runtime errors
• Incorrect initialization of result
• Misunderstanding subtraction logic

5. Given the Roman numeral string "XLIX", which of the following C++ code snippets correctly converts it to an integer?

hard

A. int romanToInt(std::string s) {
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = 0; i < s.size(); ++i) {
total += roman[s[i]];
}
return total;
}

B. int romanToInt(std::string s) {
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = 0; i < s.size(); ++i) {
if (roman[s[i]] > roman[s[i+1]]) {
total += roman[s[i]];
} else {
total -= roman[s[i]];
}
}
return total;
}

C. int romanToInt(std::string s) {
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = s.size() - 1; i >= 0; --i) {
if (roman[s[i]] < roman[s[i+1]]) {
total -= roman[s[i]];
} else {
total += roman[s[i]];
}
}
return total;
}

D. int romanToInt(std::string s) {
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = 0; i < s.size(); ++i) {
if (i + 1 < s.size() && roman[s[i]] < roman[s[i+1]]) {
total -= roman[s[i]];
} else {
total += roman[s[i]];
}
}
return total;
}

Solution

1. Step 1: Check correct subtraction logic with bounds check

   int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = 0; i < s.size(); ++i) { if (i + 1 < s.size() && roman[s[i]] < roman[s[i+1]]) { total -= roman[s[i]]; } else { total += roman[s[i]]; } } return total; } correctly checks if next character exists and if current value is less than next, then subtracts; else adds.

2. Step 2: Verify other options for errors

   int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = 0; i < s.size(); ++i) { if (roman[s[i]] > roman[s[i+1]]) { total += roman[s[i]]; } else { total -= roman[s[i]]; } } return total; } reverses logic and lacks bounds check; int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = s.size() - 1; i >= 0; --i) { if (roman[s[i]] < roman[s[i+1]]) { total -= roman[s[i]]; } else { total += roman[s[i]]; } } return total; } accesses s[i+1] when i is last index (out-of-bounds); int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = 0; i < s.size(); ++i) { total += roman[s[i]]; } return total; } adds all values ignoring subtraction rule.

3. Final Answer:

   The code in Step 1 -> Option D

4. Quick Check:

   Check bounds and subtract if current < next [OK]

Hint: Check next char exists before subtracting current [OK]

Common Mistakes:

• Not checking index bounds before accessing s[i+1]
• Reversing subtraction logic
• Ignoring subtraction rule completely