Greedy algorithm.



Arnab is playing a game. He is given a number N in string format and now he is asked to remove M digits from the number as a part of the game. He wants to return with the maximum value of N possible(Order of digits should not change). Print the maximum value of N.

See original problem statement here

For Example :

421 1

If we remove 4 ,the number obtained is 21.
If we remove 2,we get 41.
Removing 1 gives 42.

maximum of 21 ,41 and 42 is 42.


To get the maximum possible number after removing m digits, we shall remove m lowest digits.


This problem demands greedy approach.

Iterating m times and removing each digit one by one to get the maximum number for each m is basically what is required to solve the problem.

  1. Run a loop m times by referring data structures and algorithms tutorials.

  2. In each iteration, store the maximum number obtained by removing every digit from the current value of n.

  3. Consider this maximum as the current value of n and proceed to the next iteration and repeat the above step.

  4. The maximum of all these values, is the solution.


[TABS_R id=1406]
[forminator_quiz id=”1408″]

Previous post BLOCK MOVE
Next post FRACTION

Leave a Reply

Your email address will not be published. Required fields are marked *