[Solved] Consider the following Python function that returns the largest monotone increasing digits number less than or equal to n. What is the output when n = 332?... What is the output when n = 332? | Greedy Algorithms

Greedy Algorithms - Monotone Increasing Digits

Consider the following Python function that returns the largest monotone increasing digits number less than or equal to n. What is the output when n = 332?

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

print(monotoneIncreasingDigits(332))

A299

B329

C2999

D322

Step-by-Step Solution

Solution:

Step 1: Trace the loop from right to left
Digits start as [3, 3, 2]. At i=2, digits[2]=2 < digits[1]=3, so digits[1] decrements to 2 and marker=2.
Step 2: Set digits from marker to end to 9
Digits become [3, 2, 9]. Next, at i=1, digits[1]=2 < digits[0]=3, so digits[0] decrements to 2 and marker=1. Then digits from index 1 onward set to 9 -> [2, 9, 9].
Final Answer:
Option A -> Option A
Quick Check:
Final digits [2,9,9] form 299 which is largest monotone ≤ 332 [OK]

Quick Trick: Decrement and set trailing digits to 9 for monotone fix [OK]

Common Mistakes:

MISTAKES

Stopping after first decrement without rechecking previous digits
Not setting trailing digits to 9
Returning intermediate digits without full fix

Trap Explanation:

PITFALL

Candidates often miss the second decrement step or forget to set trailing digits to 9, leading to wrong output.

Interviewer Note:

CONTEXT

Tests ability to mentally execute greedy digit adjustment code correctly.

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

Consider the following Python function that returns the largest monotone increasing digits number less than or equal to n. What is the output when n = 332?

Step 1: Trace the loop from right to left

Step 2: Set digits from marker to end to 9

Final Answer:

Quick Check:

Want More Practice?