0

Given the function largestMonotoneIncreasing(n) that returns the largest number ≤ n with digits in non-decreasing order, what is the output of largestMonotoneIncreasing(321)?

easy🧾 Trace Q3 of Q15

Greedy Algorithms - Monotone Increasing Digits

Given the function largestMonotoneIncreasing(n) that returns the largest number ≤ n with digits in non-decreasing order, what is the output of largestMonotoneIncreasing(321)?

A2999

B321

C311

D299

Step-by-Step Solution

Solution:

Step 1: Analyze digits of 321
The digits are 3, 2, 1 which are decreasing.
Step 2: Find largest monotone increasing number ≤ 321
Decrease the first digit to 2 and set subsequent digits to 9 to maximize the number: 299.
Final Answer:
Option D -> Option D
Quick Check:
299 ≤ 321 and digits are non-decreasing [OK]

Quick Trick: Adjust digits left to right, then fill with 9s [OK]

Common Mistakes:

MISTAKES

Assuming 321 is monotone increasing
Not replacing digits after decrement with 9
Returning 311 which is not monotone increasing

Trap Explanation:

PITFALL

Choosing 321 or 311 seems close but digits decrease in those numbers.

Interviewer Note:

CONTEXT

Tests understanding of how to adjust digits to maintain monotonicity.

Master "Monotone Increasing Digits" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More Greedy Algorithms Quizzes