Roman to Integer

📋

Roman to Integer

Edge cases:

</>

IDE

def romanToInt(s: str) -> int:public int romanToInt(String s)int romanToInt(string s)function romanToInt(s)

def romanToInt(s: str) -> int:
    # Write your solution here
    pass

class Solution {
    public int romanToInt(String s) {
        // Write your solution here
        return 0;
    }
}

#include <string>
using namespace std;

int romanToInt(string s) {
    // Write your solution here
    return 0;
}

function romanToInt(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 4 for input 'IV' computed as 6Always adding values without subtracting when current symbol is less than next.✅ Add condition: if roman_map[s[i]] < roman_map[s[i+1]] then subtract current value instead of adding.

Wrong: 9 for input 'IX' computed as 11Incorrectly adding both symbols without subtractive logic.✅ Implement lookahead subtraction: subtract current if less than next.

Wrong: 15 for input 'VX' computed as -5Subtracting invalid pairs where smaller symbol is not allowed to subtract.✅ Only subtract if current symbol is I, X, or C and next symbol is valid larger symbol.

Wrong: 8 for input 'IVIV' computed as 6Skipping symbols after subtractive pair or double counting.✅ After subtracting, move index by one, not two, to process all symbols.

Wrong: TLE on large inputUsing nested loops or exponential complexity instead of linear scan.✅ Use single pass with lookahead subtraction logic, O(n) time complexity.

✓

Test Cases

Focus on handling single characters and the largest valid numeral correctly.

Consider tricky subtractive pairs and invalid patterns that might break naive logic.

Optimize your solution to run in linear time with constant space.

t1_01basic

Input{"s":"III"}

Expected0

⏱ Performance - must finish in 2000ms

Each 'I' adds 1, so 1 + 1 + 1 = 3.

💡 Process each Roman symbol and sum their values.

💡 Check if the current symbol is less than the next to decide subtraction.

💡 Subtract value if current < next, else add it.

Why it failed: Output incorrect for repeated symbols. Likely missed subtractive logic or always added values. Fix: subtract current value if next symbol is larger.

✓ Correctly handles repeated additive symbols.

t1_02basic

Input{"s":"LVIII"}

Expected0

⏱ Performance - must finish in 2000ms

L=50, V=5, I=1, I=1, I=1; sum = 50 + 5 + 3 = 58.

💡 Sum values of symbols, watch for subtractive pairs.

💡 No subtractive pairs here, so just add all values.

💡 Ensure no subtraction when current symbol >= next.

Why it failed: Incorrect output for numerals without subtractive pairs. Possibly subtracting incorrectly or skipping symbols. Fix: only subtract when current < next.

✓ Correctly sums symbols without subtractive pairs.

t2_01edge

Input{"s":"I"}

Expected1

⏱ Performance - must finish in 2000ms

Single character 'I' equals 1.

💡 Handle single character input correctly.

💡 No next symbol to compare, just return its value.

💡 Return value of single symbol directly.

Why it failed: Fails single character input by accessing out-of-bounds next symbol. Fix: check index bounds before lookahead.

✓ Handles single character input without errors.

t2_02edge

Input{"s":"MMMCMXCIX"}

Expected0

⏱ Performance - must finish in 2000ms

Largest valid numeral: M=1000*3 + CM=900 + XC=90 + IX=9 = 3999.

💡 Test upper boundary of input size and value.

💡 Ensure subtractive pairs at multiple positions handled.

💡 Correctly combine additive and subtractive values.

Why it failed: Fails on largest numeral due to incorrect subtractive pair handling or overflow. Fix: implement subtractive logic consistently for all pairs.

✓ Correctly converts largest valid Roman numeral.

t2_03edge

Input{"s":"IX"}

Expected0

⏱ Performance - must finish in 2000ms

Subtractive pair 'IX' equals 10 - 1 = 9.

💡 Check subtractive pairs at string end.

💡 Look ahead to next symbol to decide subtraction.

💡 Subtract current if less than next symbol.

Why it failed: Fails subtractive pair at end by adding both symbols. Fix: subtract current value if next symbol is larger.

✓ Correctly handles subtractive pairs at string end.

t2_04edge

Input{"s":"VIII"}

Expected0

⏱ Performance - must finish in 2000ms

No subtractive pairs, sum all symbols: V=5 + I=1 + I=1 + I=1 = 8.

💡 Test input with no subtractive pairs.

💡 Sum all symbol values directly.

💡 Ensure no subtraction logic triggers incorrectly.

Why it failed: Incorrectly subtracts symbols when none should be subtracted. Fix: only subtract when current < next.

✓ Correctly sums symbols without subtractive pairs.

t3_01corner

Input{"s":"IVIV"}

Expected0

⏱ Performance - must finish in 2000ms

IV=4 + IV=4 total 8; tests repeated subtractive pairs.

💡 Check handling of multiple subtractive pairs in sequence.

💡 Ensure subtractive logic applies for each pair independently.

💡 Do not skip symbols after subtractive pair; process all.

Why it failed: Fails repeated subtractive pairs by skipping symbols or miscounting. Fix: after subtracting, move index by one, not two.

✓ Correctly processes multiple subtractive pairs in sequence.

t3_02corner

Input{"s":"VX"}

Expected0

⏱ Performance - must finish in 2000ms

V=5 + X=10 = 15; tests invalid subtractive pair (V cannot subtract).

💡 Roman numerals only subtract if smaller symbol precedes larger valid symbol.

💡 Check if current symbol is valid for subtraction.

💡 If invalid subtractive pair, add values instead.

Why it failed: Incorrectly subtracts invalid pairs like 'VX'. Fix: only subtract if current symbol is I, X, or C and next is valid larger symbol.

✓ Correctly ignores invalid subtractive pairs.

t3_03corner

Input{"s":"IIII"}

Expected0

⏱ Performance - must finish in 2000ms

Four 'I's equal 4; tests no subtractive pair but repeated symbols beyond standard rules.

💡 Handle repeated symbols even if input is non-standard but valid per problem.

💡 Sum all symbols if no subtractive pairs.

💡 Do not assume max repeats; problem states input is valid.

Why it failed: Fails repeated symbols by limiting count or expecting subtractive pairs. Fix: sum all symbols if no subtractive pair detected.

✓ Correctly sums repeated symbols without subtractive pairs.

t4_01performance

Input{"s":"MCMXCMXCMXCMXCMXCMXCMXCMXIX"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length 29, must complete in O(n) time within 2 seconds.

💡 Algorithm should run in linear time O(n).

💡 Avoid nested loops or exponential checks.

💡 Use single pass with lookahead subtraction logic.

Why it failed: TLE due to nested loops or exponential complexity. Fix: implement single pass O(n) solution with constant space.

✓ Algorithm runs in O(n) time confirming efficiency.

Practice

1. You need to find the smallest positive number that is divisible by two given integers, and also find the greatest integer that divides both. Which approach guarantees the most efficient and reliable solution for this problem?

easy

A. Use a brute force search checking multiples and divisors until the answer is found.

B. Use a greedy algorithm that picks the largest divisor first and tries to build the LCM.

C. Apply the Euclidean algorithm iteratively to find GCD, then compute LCM using the GCD.

D. Use dynamic programming to store intermediate divisors and multiples for both numbers.

Solution

1. Step 1: Understand the problem requirements

   The problem requires finding the greatest common divisor (GCD) and least common multiple (LCM) of two integers efficiently.

2. Step 2: Evaluate approaches

   Brute force is inefficient for large inputs. Dynamic programming and greedy approaches do not naturally fit this problem. The Euclidean algorithm efficiently computes GCD in O(log(min(a,b))) time, and LCM can be derived from GCD.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Euclidean algorithm is the standard optimal method for GCD and LCM [OK]

Hint: Euclidean algorithm efficiently finds GCD and LCM [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Confusing greedy with Euclidean algorithm

2. Consider the following code snippet that checks if a number is a palindrome by reversing half of its digits. What is the value of reversed_half after the second iteration of the while loop when input is 12321?

easy

A. 12

B. 1

C. 21

D. 123

Solution

1. Step 1: Trace first iteration

   Initial x=12321, reversed_half=0 reversed_half = 0*10 + 12321%10 = 1 x = 12321 // 10 = 1232

2. Step 2: Trace second iteration

   reversed_half = 1*10 + 1232%10 = 10 + 2 = 12 x = 1232 // 10 = 123

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   After two iterations reversed_half is 12 [OK]

Hint: Track variable updates carefully each loop iteration [OK]

Common Mistakes:

• Off-by-one iteration count
• Mixing x and reversed_half values
• Incorrect modulo or division

3. You need to find the nth number whose prime factors only include 2, 3, and 5. Which approach guarantees an optimal solution that efficiently generates these numbers without checking every integer sequentially?

easy

A. Use a min-heap (priority queue) to always extract the smallest candidate and generate new multiples, avoiding duplicates.

B. Use a greedy algorithm that picks the smallest next multiple of 2, 3, or 5 from previously found numbers.

C. Use dynamic programming with a 2D table to store all factors and their counts for each number up to n.

D. Use brute force by checking each integer sequentially and verifying if its prime factors are only 2, 3, and 5.

Solution

1. Step 1: Understand the problem constraints

   The problem requires generating numbers whose prime factors are only 2, 3, and 5, known as ugly numbers.

2. Step 2: Evaluate approaches for efficiency and correctness

   Brute force is too slow; min-heap approach is efficient but can be optimized further; dynamic programming with a 2D table is overcomplicated. The greedy approach with three pointers picks the smallest next multiple of 2, 3, or 5 from previously found numbers, efficiently generating the sequence without duplicates.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Three-pointer greedy approach efficiently generates ugly numbers in ascending order without duplicates [OK]

Hint: Three-pointer greedy approach avoids duplicates and generates numbers in order [OK]

Common Mistakes:

• Assuming min-heap is the only efficient approach
• Thinking DP with 2D table is needed for prime factorization
• Believing brute force is efficient enough for large n

4. Consider the following buggy code snippet for converting an Excel column title to a number. Which line contains the subtle bug that causes incorrect results for inputs like "A" or "Z"?

medium

A. Line 4: powers computation loop

B. Line 7: initialization of result

C. Line 9: calculation of value using zero-based indexing

D. Line 10: accumulation of result using powers

Solution

1. Step 1: Identify how letter values are computed

   The code uses ord(ch) - ord('A'), which makes 'A' = 0 instead of 1.

2. Step 2: Understand impact on result

   This causes all results to be off by one, e.g., "A" returns 0 instead of 1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct letter values must be 1-based, not zero-based [OK]

Hint: Check if 'A' maps to 1, not 0 [OK]

Common Mistakes:

• Using zero-based indexing for letters
• Miscomputing powers array
• Incorrect accumulation order

5. The following code attempts to determine if a number is happy but contains a subtle bug. Identify the line with the bug.

def isHappy(n: int) -> bool:
    def digit_square_sum(num: int) -> int:
        total = 0
        while num > 0:
            digit = num % 10
            total += digit * digit
            num //= 10
        return total

    while n != 1:
        n = digit_square_sum(n)
    return True

medium

A. Line with 'while n != 1:' loop condition

B. Missing cycle detection causing infinite loop

C. Line with 'return True' after the loop

D. Line with 'n = digit_square_sum(n)' inside the loop

Solution

1. Step 1: Analyze loop termination condition

   The loop only terminates when n == 1, but if n falls into an unhappy cycle, it never reaches 1.

2. Step 2: Identify missing cycle detection

   Without tracking seen numbers or using a known cycle set, the code loops infinitely for unhappy numbers.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Infinite loop occurs due to missing cycle detection [OK]

Hint: No cycle detection -> infinite loop on unhappy numbers [OK]

Common Mistakes:

• Assuming loop condition suffices
• Ignoring cycle detection necessity
• Misreading return placement