Remove K Digits

Posted: 12 Apr, 2021
Difficulty: Moderate


Try Problem

You are given a non-negative integer ‘NUM’ in the form of a string and provided with an integer ‘K’. You need to find out the smallest integer possible by removing exactly ‘K’ digits from ‘NUM.’

Note :
 ‘NUM’ does not have leading zeros except when ‘NUM’ is equal to zero.
Input Format :
The first line contains an integer, ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.

The first line of each test case contains a string ‘NUM’ and integer ‘K.’
Output Format :
For each test case, print a single string, the minimum integer that can be possibly made by removing ‘K’ digits from ‘NUM’.

Output for each test case will be printed in a separate line.
Note :
You don’t have to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <=10
2 <= |NUM| <= 10^5
0 <= K <= |NUM|

Where |NUM| denotes the length of the initial string ‘NUM’ and ‘K’ denotes the number of digits to be removed. 

Time limit: 1 second
Approach 1
  • This is the brute force solution, hence we will use recursion to compute the required integer of size ‘N’ - ‘K’.
  • For each digit in the initial string “NUM” we have 2 options, either it is present in the current answer or it is not. Hence we can create a function findAll() which takes the following parameters:
    • The initial string ‘NUM’.
    • The current index ‘IDX’ which we either choose or not.
    • String ‘CUR’ the answer from index 0 to ‘IDX’
    • A variable ‘REMAIN’ which denotes how many digits are remaining to be added in the answer.
  • Initially, ‘IDX’ is equal to 0 and goes till ‘N’, ‘REMAIN’ is equal to ‘N’ - ‘K’ and ‘CUR’ is empty.
  • Whenever we choose a digit to include in the answer ‘REMAIN’ decreases by 1 and we move to the next ‘IDX’(i.e ‘IDX’ + 1). When ‘REMAIN’ is equal to 0 that means we have selected ‘N’ - ‘K’ digits and hence can compare if the current answer is minimum amongst all of the possible answers or not.
Try Problem