# Remove K Digits

Posted: 12 Apr, 2021
Difficulty: Moderate

## 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 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.