Smallest Number after Removing K digits
Objective: Given a number with N digits, write a program to get the smallest number possible after removing k digits from number N.
Implement a method that returns the lowest possible number that could be generated after removing n characters from a string of digits.
N = 1453287, k = 3 Output: 1287 N = 4321, k=2 Output: 21 N = 22222, k=3 Output: 22
Approach: Use Stack
- Iterate through the given number from left to right, one digit at a time.
- while k> && stack is not empty and top element in the stack is greater than current digit
- If yes then, pop out the top element from the stack.
- Reduce the k by 1.
- Push the current digit to stack.
- while k is greater than 0.
- pop-out elements from the stack.
- Reduce the k by 1
- Pull all the digits from the stack and construct the number and reverse it, this will be the final answer. (if there are 0 at the start of the answer, remove those).
- See the code below for more understanding.
Input: 1453287, k: 3 Smallest number after removing 3 digits: 1287
Top Companies Interview Questions..-
If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.