PROBLEM LINK:
Author: shakil ahmed
DIFFICULTY:
EASY.
PREREQUISITES:
Greedy
PROBLEM:
Given a number of N digits. After erasing exactly M digits what should be the highest number.
QUICK EXPLANATION:
We can solve this problem by greedy approach . Starting from left side we can remove this number if and one if another number ( which is in right form current number ) is greater than this or we are in that situation we need to remove all remaining numbers . Lets consider first example . Here we have 591 from this we have to remove one number . we always start from first number in left most number which is 5 and from its right there is 9 which is greater than 5 so we have to remove 5 in order to get a bigger number. Time complexity O(N^2) .
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.