Friday, March 20, 2015

Minimum number after removing K digits

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.