How to get the least number after deleting k digits from the input number

Question

For example, if the input number is 24635, the least number is 23 after deleting any 3 digits.

It's not the same as taking the two smallest digits, because the order of the digits must be maintained.

Answer 1

Deleting k digits means keeping n - k digits, where n is the total number of digits.

Use a stack that you keep sorted ascendingly. You remove elements from it as long as you can still make it to n - k digits and your current element is smaller than the top of the stack:

push(2) => 2
push(4) because 2 < 4 => 24
push(6) because 4 < 6 => 246
pop() because 3 < 6 and we can still end up with 2 digits => 24
pop() for the same reason => 2
push(3) => 23
push(5) => 235

Then just take the first k digits => 23. Or you can make sure never to push more than k digits, and then the final stack is your solution.

Note that you cannot pop elements if that means you will not be able to build a solution of k digits. For this, you need to check the current number of elements in the stack and the number of digits to the right of your current position on the input number.

Pseudocode:

stack = []
for each d in digits:
  while !stack.empty() and d < stack.top() and (*):
    stack.pop()

  if stack.size() < n - k:
    stack.push(d)

 (*) - exercise, fill in the condition that prevents you 
       from popping elements if you still want to be able to get to a solution.
 Hint: count how many elements the for loop went over already
       and see how many are left. Also consider how many you have left in the stack.

Since each element enters and leaves the stack at most once, the complexity is O(n).

Answer 2

Offer a recursive approach.

On each iteration test for success k == 0 ...
or failure num == 0 as there are no digits left to remove.
(returning 10 is worse than some other path that would return num.)

Otherwise recurse in 2 ways:
1) Keep the least-significant-digit and try with upper digits.
2) Drop the least-significant-digit and try with upper digits, k--
Return the better one.

unsigned reduce(unsigned num, unsigned k) {
  if (k <= 0) {
    return num;  // Success
  }
  if (num == 0) {
    return 10;  // Fail
  }
  unsigned path1 = reduce(num/10, k)*10 + num%10;
  unsigned path2 = reduce(num/10, k-1);
  return path1 < path2 ? path1 : path2;
}

int main(void) {
  printf("%u\n", reduce(246, 2));
  printf("%u\n", reduce(24635, 3));
  printf("%u\n", reduce(53642, 3));
  printf("%u\n", reduce(21, 1));
}

2
23
32
1

This solution does not depend on knowing the number of digits, just the number needed to remove.