Remove K Digits

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

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 )
Input Format :
The first line of the input contains the string 'num'.

The second line contains the integer 'k'.
Output Format :
For each test case, return a string, the minimum integer that can be made by removing ‘k’ digits from ‘num’.
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. 
Hint

If we remove ‘k’ digits from the initial number of say, length ‘n’, then the length of our answer will be ‘n’ - ‘k'. Find all the integers you can create from ‘num’ of length ‘n’ - ‘k’  and output the minimum amongst them.

Approaches (3)
Brute Force
  • 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’ denotes how many digits remain 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.
Time Complexity

O(2^n), where ‘n’ is the length of the string ‘num.’

 

For every character in ‘num’, we have 2 options, either we include it in the current answer ‘cur’ or not. Hence, we have two options for each of the ‘n’ characters, making the total time complexity O(2^n).

Space Complexity

O(n), where ‘n’ is the length of the string ‘num.’

 

We use recursion to find the optimal answer. For a recursive call stack, the space complexity is always proportional to the depth of the recursive call tree, which is equal to ‘n’. Hence space complexity is O(n).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Remove K Digits
Full screen
Console