[Solved] What is the subtle bug causing incorrect results on some inputs?def monotone_increasing_buggy(n): digits = list(map(int, str(n))) for i in range(1, len(digits)): if digits[i] | Greedy Algorithms

Greedy Algorithms - Monotone Increasing Digits

Examine the following code snippet intended to find the largest monotone increasing digits number ≤ n. What is the subtle bug causing incorrect results on some inputs?

def monotone_increasing_buggy(n):
    digits = list(map(int, str(n)))
    for i in range(1, len(digits)):
        if digits[i] < digits[i-1]:
            digits[i-1] -= 1
            digits[i:] = [9] * (len(digits) - i)
    return int(''.join(map(str, digits)))

AIncorrectly replaces digits with zeros instead of nines

BFails to propagate decrement backward when needed

CDoes not convert digits back to integer before returning

DUses a for loop instead of a while loop causing infinite loop

Step-by-Step Solution

Solution:

Step 1: Understand the decrement step
When a digit is less than the previous, the previous digit is decremented.
Step 2: Identify missing backward propagation
If decrementing the previous digit causes it to be less than its own previous digit, the code does not continue adjusting earlier digits.
Step 3: Consequence
This leads to incorrect results for inputs like 332 where multiple backward adjustments are needed.
Final Answer:
Option B -> Option B
Quick Check:
Check inputs needing multiple decrements [OK]

Quick Trick: Decrement may cascade backward; code misses this [OK]

Common Mistakes:

MISTAKES

Assuming single decrement fixes all violations
Ignoring need to re-check previous digits after decrement
Confusing digit replacement values

Trap Explanation:

PITFALL

Decrementing only once looks correct but misses cascading fixes.

Interviewer Note:

CONTEXT

Tests debugging skills and understanding of algorithm correctness.

Master "Monotone Increasing Digits" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Greedy Algorithms Quizzes

Examine the following code snippet intended to find the largest monotone increasing digits number ≤ n. What is the subtle bug causing incorrect results on some inputs?

Step 1: Understand the decrement step

Step 2: Identify missing backward propagation

Step 3: Consequence

Final Answer:

Quick Check:

Want More Practice?