Remove K Digits
Posted: 12 Apr, 2021
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.’
‘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.
You don’t have to print anything. It has already been taken care of. Just implement the given function.
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
- 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.
Ninja And Alternating Largest
Posted: 14 Jun, 2021
Posted: 15 Jun, 2021
Break The Prison
Posted: 17 Jun, 2021
PostFix To Prefix
Posted: 24 Jun, 2021
Queue using Array or Singly Linked List.
Posted: 27 Jul, 2021