Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Remove K Digits

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
33 upvotes
Asked in companies
FacebookMicrosoftMakeMyTrip

Problem statement

You are given a non-negative integer ‘num’ in the form of a string and provided with an integer ‘k’.


You need to find the smallest integer possible by removing exactly ‘k’ digits from ‘num.’


Note :
‘num’ does not have leading zeros except when ‘num’ equals zero.
Example:
Input: ‘num’ = ‘141’ , ‘k’ = 1.

Output: ‘11’

Explanation: By removing only 1 digit from ‘num’, 3 numbers can be formed: 14, 11, and 41. Out of which 11 is the smallest number.
Note :
You don’t have to print anything. It has already been taken care of. Just implement the given function.
Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1 :
123
1
Sample Output 1 :
12
Explanation For Sample Input 1 :
We can remove the last digit, ‘3’ to get the smallest possible answer, ‘12’.

Other possible answers are ‘23’ and ‘13’, all of which are greater than ‘12’.
Sample Input 2 :
3214
2
Sample Output 2 :
14
Explanation For Sample Input 2:
In this case, six numbers can be formed: 32, 31, 34, 21, 24, 14.
Out of which 14 is the smallest.
Expected time complexity:
The expected time complexity is O(n).
Constraints :
2 <= |num| <= 10^6
0 <= k <= |num|

Time limit: 1 second

Where |num| denotes the length of the initial string ‘num’ and ‘k’ represents the number of digits to be removed. 
Full screen
Console