1
$\begingroup$

I have a number with $n$ digits. I want to keep only $m$ digits out of it. What is the smallest possible $m$ digit number which can be generated from the larger number so that order of digits is retained.

Ex: 3422509739

I need the smallest 3 digit number by removing 7 digits with order retained which will be 039.

$\endgroup$
1
$\begingroup$

This problem is very similar to subsequence problem that is solved using dynamic programming. So, there are several ways to solve this problem, but the algorithm that you choose really depends on the input size ($n$, $m$ and base of numbers).

I here explain the simplest algorithm. I assume that the number is given in base 10, which means that your digits are all between 0 and 9. You just need to iterate over the smallest digits first and construct the smallest possible subnumber from the digits after that.

Algorithm SmallestSubNumber(number[1:n], m)
Smallest = \inf;
For i=0:9
   For j=1:n-m
      If (number[j] == i):
          Smallest = min(Smallest, i*10^(m-1) + SmallestSubNumber(number[j+1:n], m-1));
   If (Smallest != \inf) return Smallest;
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.