Given a number N, and a number K, find the minimum number that can be formed by deleting K digits. The order of the digits should not be changed.
For example consider N = 234987, K = 2, we can remove 9,8 and the resulting number is 2347.
The solution is based on the following observation, consider the above case.
Let us delete a digit from 234987
Deleted Digit – Result
—————————
2 – 34987
3 – 24987
4 – 23987
9 – 23487
8 – 23497
7 – 23498
If we remove 9 we will get the minimum number. Observe that in the given number, 9 is the first digit which is greater than the next digit.
What if all the digits are in ascending order?
Let us walk through an example.
N = 12345, K = 3. If we remove 4,5 we will get the minimum number. The observation is that we need to keep on removing right-most digits in this case.
[This is a re-post after correcting my incorrect approach. Thanks to Jeff Senecal for pointing out the mistake.]
Here is the C++ implementation of the above approach.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <string> | |
| #include <vector> | |
| using namespace std; | |
| string getMinRemoveK(const string& num, int k) | |
| { | |
| string result = num; | |
| if( k <= 0 )//trivial case; error handling | |
| return num; | |
| else if( num.size() > 0 && num.size() > k ) | |
| { | |
| int i; | |
| for( i = 0; i < k; i++ ) | |
| { | |
| int digit_index; | |
| for(digit_index = 0; digit_index < result.size()-1; digit_index++ ) | |
| { | |
| if( result[digit_index] > result[digit_index+1] ) | |
| { | |
| result.erase(result.begin() + digit_index); | |
| break; | |
| } | |
| } | |
| if( digit_index == result.size()-1 ) | |
| { | |
| result.erase(result.end()-1); | |
| } | |
| } | |
| } | |
| return result; | |
| } | |
| int main() | |
| { | |
| cout << getMinRemoveK("670124", 2) << endl;//prints 0124 | |
| cout << getMinRemoveK("8361957", 3) << endl;//prints 1957 | |
| cout << getMinRemoveK("13", 1) << endl;//prints 1 | |
| cout << getMinRemoveK("9999", 2) << endl;// prints 99 | |
| cout << getMinRemoveK("1000", 0) << endl;//prints 1000 | |
| cout << getMinRemoveK("8561357", 3) << endl;//prints 1357 | |
| cout << getMinRemoveK("12311", 1) << endl;//prints 1211 | |
| return 0; | |
| } |
by