Problem Statement:
You are given a number and integer k.
You need to remove k digits from the number and it should return the smallest integer possible.
Example
Input: num = “10300”, k = 1
Output: “300”
Here if you remove the leading “1”, the o/p will be the smallest integer possible.
Solution
Here we need the smallest integer, so we need to use greedy method.
We need to start from the most significant digit and remove it and check if we can get a smaller number.
Else we go to the next element.
For the solution we will use the stack.
Initially we push the element into the stack.
Then when we get the next element, we check if it is smaller than the element inside the stack. Then we pop the top element from the stack and push this element.
Because we need to get the smaller number. Finally the element present inside the stack are the smallest element.
Example:
Number = 2674, k = 2
DIGITS = 2, 6, 7, 4 K = 2 res = “”
current digit = 2, So, res_stack = 2
current digit = 6, So, res_stack = 26
current digit = 7, So, res_stack = 267
current digit = 4,
Now, previous digit “7” greater than current digit “4.
Hence pop the element from the stack and decrement k value.
res_stack = 26 K = 1
But still previous digit “6” is greater than current digit “4”
res_stack = 2, K = 0
As k became 0, we get the result.
res_stack = 24
Solution in C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
string remove_k_digits(string num, int k)
{
string ans="";
for(char &c:num)
{
while(ans.size() && ans.back()>c &&k)
{
ans.pop_back();
k--;
}
if(ans.size()||c!='0')ans.push_back(c);
}
while(ans.size()&&k--)
{
ans.pop_back();
}
return (ans=="")?"0":ans;
}
int main()
{
string num = "2674";
int k = 2;
cout << "The min number is = "<<remove_k_digits(num, k)<<endl;
return 0;
}Output:
The min number is = 24