Jahirul Islam Monir Jahirul Islam Monir - 2 months ago 13
C++ Question

How to get the maximum number after erasing n digits from the number

For ex. if the number is 9511145 if I want to delete 3 least digits from this number the maximum number will be 9545.Deleted digits no need to be contiguous.But digits of the maximum number will remain of their original order. The number can be 10^6 digits long.To solve this problem in iterative approach it could take O(N^2) time.If anyone could suggest any better approach to solve this problem then it would be great help.Thanks in advance.

Answer

The solution to this question has been beautifully answered here. Only difference is you have to keep the stack sorted decreasingly.

# process digits from left to right
for each digit from left to right
  if digit <= top of the stack
    push(digit)
    continue
  while (digit > top of the stack) and (we have enough digits to reach n-k digits)
    pop()
  push(digit)
pop extra digits

9511145
push(9) => 9
push(5) because 5 <= 9 => 95
push(1) because 1 <= 5 => 951
push(1) because 1 <= 1 => 9511
push(1) because 1 <= 1 => 95111
pop() because 4 > 1 and we can still end up with 4 digits => 9511
pop() because 4 > 1 and we can still end up with 4 digits => 951
pop() because 4 > 1 and we can still end up with 4 digits => 95
push(4) because 4 <= 5 => 954
push(5) because we need to have 4 digits at least => 9545

NOTE: upvote original answer.

Comments