Roman to Integer

▶

Steps

setup

Initialize Input and Result

The input string 'III' is converted into an array of characters. The result variable is initialized to zero to start accumulating the integer value.

💡 Starting with a clear input array and a zero result sets the stage for processing each Roman numeral symbol one by one.

Line:

result = 0

💡 The algorithm needs a starting point for accumulation and a way to access each character.

traverse

Get Value of Current Symbol 'I'

The algorithm calls the value function to get the integer value of the current symbol 'I' at index 0, which is 1.

💡 Mapping Roman symbols to integers is essential to perform arithmetic operations.

Line:

curr = value(s[i])

💡 Each Roman character corresponds to a fixed integer value.

traverse

Get Value of Next Symbol 'I'

The algorithm gets the value of the next symbol at index 1, which is also 'I' with value 1.

💡 Looking ahead to the next symbol helps decide whether to add or subtract the current value.

Line:

next_val = value(s[i + 1]) if i + 1 < len(s) else 0

💡 Comparing current and next values determines addition or subtraction.

compare

Compare Current and Next Values (1 vs 1)

Since current value (1) is not less than next value (1), the algorithm decides to add the current value to the result.

💡 This comparison is the core rule that distinguishes addition from subtraction in Roman numerals.

Line:

if curr < next_val:
    result -= curr
else:
    result += curr

💡 When current value is greater or equal to next, add it to the result.

traverse

Move Pointer to Next Symbol at Index 1

The pointer moves forward to index 1 to process the next symbol 'I'.

💡 Advancing the pointer ensures each symbol is processed in order.

Line:

for i in range(len(s)):

💡 The algorithm processes symbols sequentially from left to right.

traverse

Get Value of Current Symbol 'I' at Index 1

The algorithm gets the value of the symbol 'I' at index 1, which is 1.

💡 Each symbol's value is retrieved to decide how to update the result.

Line:

curr = value(s[i])

💡 The value function is called repeatedly for each symbol.

traverse

Get Value of Next Symbol 'I' at Index 2

The algorithm gets the value of the next symbol 'I' at index 2, which is 1.

💡 Looking ahead to the next symbol is necessary for the addition/subtraction decision.

Line:

next_val = value(s[i + 1]) if i + 1 < len(s) else 0

💡 The next symbol's value is always checked unless at the end of the string.

compare

Compare Current and Next Values (1 vs 1) at Index 1

Since current value (1) is not less than next value (1), the algorithm adds current value to the result.

💡 The same addition rule applies for equal or greater current values.

Line:

if curr < next_val:
    result -= curr
else:
    result += curr

💡 The addition rule is consistent for repeated symbols.

traverse

Move Pointer to Last Symbol at Index 2

The pointer moves to index 2 to process the last symbol 'I' in the string.

💡 Processing the last symbol completes the iteration over the input.

Line:

for i in range(len(s)):

💡 The algorithm processes all symbols sequentially.

traverse

Get Value of Current Symbol 'I' at Index 2

The algorithm gets the value of the last symbol 'I' at index 2, which is 1.

💡 Even the last symbol must be processed to complete the conversion.

Line:

curr = value(s[i])

💡 The value function is called for every symbol, including the last.

traverse

Get Value of Next Symbol (None) at Index 3

Since index 3 is beyond the string length, next_val is set to 0 indicating no next symbol.

💡 Handling the end of the string prevents errors and finalizes the addition.

Line:

next_val = value(s[i + 1]) if i + 1 < len(s) else 0

💡 The algorithm safely handles the last symbol by assuming next value zero.

compare

Compare Current and Next Values (1 vs 0) at Last Symbol

Since current value (1) is not less than next value (0), the algorithm adds current value to the result.

💡 The last symbol is always added because there is no next symbol to compare.

Line:

if curr < next_val:
    result -= curr
else:
    result += curr

💡 The last symbol contributes positively to the total.

reconstruct

Return Final Result

The algorithm completes the iteration and returns the accumulated result 3 as the integer value of 'III'.

💡 Returning the final result completes the conversion process.

Line:

return result

💡 The sum of all additions gives the correct integer value.

def value(c: str) -> int:
    if c == 'I': return 1  # STEP 2,6,10
    if c == 'V': return 5
    if c == 'X': return 10
    if c == 'L': return 50
    if c == 'C': return 100
    if c == 'D': return 500
    if c == 'M': return 1000
    return 0

def romanToInt(s: str) -> int:
    result = 0  # STEP 1
    for i in range(len(s)):  # STEP 5,9,12
        curr = value(s[i])  # STEP 2,6,10
        next_val = value(s[i + 1]) if i + 1 < len(s) else 0  # STEP 3,7,11
        if curr < next_val:  # STEP 4,8,12
            result -= curr
        else:
            result += curr
    return result  # STEP 13

if __name__ == '__main__':
    test_cases = ['III', 'IV', 'IX', 'LVIII', 'MCMXCIV']
    for tc in test_cases:
        print(f'{tc} -> {romanToInt(tc)}')

📊

Roman to Integer - Watch the Algorithm Execute, Step by Step

Watching each character processed and how the algorithm decides to add or subtract values helps you understand the logic behind Roman numeral conversion without guessing.

setup

i

I

0

I

1

I

2

Result: 0

compare

i

I

0

I

1

I

2

Result: 0

compare

i

I

0

next

I

1

I

2

Result: 0

compare

i

I

0

next

I

1

I

2

Result: 1

move_right

I

0

i

I

1

I

2

Result: 1

compare

I

0

i

I

1

I

2

Result: 1

compare

I

0

i

I

1

next

I

2

Result: 1

compare

I

0

i

I

1

next

I

2

Result: 2

move_right

I

0

I

1

i

I

2

Result: 2

compare

I

0

I

1

i

I

2

Result: 2

compare

I

0

I

1

i

I

2

Result: 2

compare

I

0

I

1

i

I

2

Result: 3

record

I

0

I

1

I

2

Result: 3

Key Takeaways

✓ The algorithm processes each Roman numeral symbol once, comparing it to the next to decide addition or subtraction.

This insight is hard to see from code alone because the subtraction rule is embedded in a simple if condition, but the visualization shows the pointer and values explicitly.

✓ When the current symbol's value is less than the next, it is subtracted; otherwise, it is added.

Seeing this decision visually clarifies the core Roman numeral rule that can be confusing when only reading code.

✓ The last symbol is always added because there is no next symbol to compare.

This edge case is subtle in code but clear in the visualization where the next pointer goes beyond the array and next_val is zero.

Practice

1. Consider the following Python code that checks if a number is happy using a known unhappy cycle set. What is the output when the input is 7?

def isHappy(n: int) -> bool:
    unhappy_cycle = {4, 16, 37, 58, 89, 145, 42, 20}

    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 and n not in unhappy_cycle:
        n = digit_square_sum(n)
    return n == 1

print(isHappy(7))

easy

A. True

B. False

C. The code runs indefinitely (infinite loop)

D. Raises an exception

Solution

1. Step 1: Trace digit_square_sum for input 7

   7 -> 7² = 49; next iteration: 4² + 9² = 16 + 81 = 97; then 9² + 7² = 81 + 49 = 130; then 1² + 3² + 0² = 1 + 9 + 0 = 10; then 1² + 0² = 1 + 0 = 1.

2. Step 2: Check loop termination condition

   Since n reaches 1, the loop exits and returns True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   7 is a known happy number and code returns True [OK]

Hint: 7 leads to 1 after sum-of-squares iterations [OK]

Common Mistakes:

• Confusing unhappy cycle detection
• Miscomputing digit squares
• Assuming infinite loop

2. Examine the following buggy Python code intended to compute the LCM safely without overflow:

def gcd_iterative(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm_safe(a, b):
    gcd = gcd_iterative(a, b)
    return a * b // gcd

if __name__ == '__main__':
    a, b = 1000000, 1000000
    print("LCM =", lcm_safe(a, b))

What is the subtle bug in this code?

medium

A. Line 7: Multiplying a and b before dividing by gcd can cause integer overflow.

B. Line 3: The Euclidean algorithm lacks a base case for recursion.

C. Line 9: The input values are not validated for being positive integers.

D. Line 2: The while loop condition should be 'while a != 0' instead of 'while b != 0'.

Solution

1. Step 1: Analyze lcm_safe function

   The function computes LCM as a * b // gcd. Multiplying a and b first can overflow for large inputs before division.

2. Step 2: Identify the bug

   To avoid overflow, division by gcd should happen before multiplication: (a // gcd) * b.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Multiplying large numbers before division risks overflow [OK]

Hint: Divide before multiply to avoid overflow in LCM calculation [OK]

Common Mistakes:

• Ignoring overflow risk in LCM calculation
• Misunderstanding Euclidean algorithm base case

3. 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

4. Consider the following code snippet intended to find the minimum area rectangle from a list of points. Which line contains a subtle bug that can cause incorrect results?

def minAreaRect(points):
    point_set = set(map(tuple, points))
    min_area = float('inf')
    n = len(points)
    for i in range(n):
        for j in range(i+1, n):
            x1, y1 = points[i]
            x2, y2 = points[j]
            if x1 == x2 or y1 == y2:
                continue
            if (x1, y2) in point_set and (x2, y1) in point_set:
                area = abs(x1 - x2) * abs(y1 - y2)
                if area < min_area:
                    min_area = area
    return min_area

medium

A. Line checking if x1 == x2 or y1 == y2 to skip invalid diagonals

B. Line calculating area as abs(x1 - x2) * abs(y1 - y2)

C. Line returning min_area without checking if it is still infinity

D. Line creating the point_set from points

Solution

1. Step 1: Identify the return statement

   The code returns min_area directly, which may be float('inf') if no rectangle is found.

2. Step 2: Understand the consequence

   Returning float('inf') is incorrect; the function should return 0 if no rectangle exists.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Return without check -> wrong output if no rectangle [OK]

Hint: Always check if min_area updated before returning [OK]

Common Mistakes:

• Forgetting to return 0 if no rectangle found
• Skipping diagonal check conditions

5. Suppose the Excel column titles can now include lowercase letters (a-z) in addition to uppercase (A-Z), where 'a' corresponds to 1 and 'z' to 26, independent of uppercase letters. How should the algorithm be modified to correctly convert such titles to numbers?

hard

A. Convert all letters to uppercase and use existing logic

B. Treat uppercase letters as base-26 digits and lowercase letters as separate base-26 digits, then sum

C. Use a combined mapping where 'A'-'Z' and 'a'-'z' both map to 1-26, then apply base-26 logic

D. Map uppercase and lowercase letters separately to 1-26 and multiply by 52 instead of 26

Solution

1. Step 1: Understand the new character set

   Now there are 52 possible characters (A-Z and a-z), each mapping to 1-26 independently.

2. Step 2: Adjust base and mapping accordingly

   Since there are 52 distinct characters, the base must be 52, and mapping must distinguish uppercase and lowercase letters.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Base must match character set size; 26 is insufficient for mixed case [OK]

Hint: Base equals number of distinct characters [OK]

Common Mistakes:

• Ignoring case difference
• Using base 26 for 52 chars
• Mapping lowercase to same as uppercase