Given number N eliminate K digits to get maximum possible number

Question

As the title says, the task is:

Given number N eliminate K digits to get maximum possible number. The digits must remain at their positions.

Example: n = 12345, k = 3, max = 45 (first three digits eliminated and digits mustn't be moved to another position).

Any idea how to solve this?
(It's not homework, I am preparing for an algorithm contest and solve problems on online judges.)

1 <= N <= 2^60, 1 <= K <= 20.

Edit: Here is my solution. It's working :)

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cmath>

using namespace std;


int main()
{
    string n;
    int k;

    cin >> n >> k;

    int b = n.size() - k - 1;
    int c = n.size() - b;
    int ind = 0;
    vector<char> res;
    char max = n.at(0);

    for (int i=0; i<n.size() && res.size() < n.size()-k; i++) {
        max = n.at(i);
        ind = i;
        for (int j=i; j<i+c; j++) {
            if (n.at(j) > max) {
                max = n.at(j);
                ind = j;
            }
        }

        b--;
        c = n.size() - 1 - ind - b;
        res.push_back(max);
        i = ind;
    }

for (int i=0; i<res.size(); i++)
    cout << res.at(i);

cout << endl;

    return 0;
}

Answer 1

Brute force should be fast enough for your restrictions: n will have max 19 digits. Generate all positive integers with numDigits(n) bits. If k bits are set, then remove the digits at positions corresponding to the set bits. Compare the result with the global optimum and update if needed.

Complexity: O(2^log n * log n). While this may seem like a lot and the same thing as O(n) asymptotically, it's going to be much faster in practice, because the logarithm in O(2^log n * log n) is a base 10 logarithm, which will give a much smaller value (1 + log base 10 of n gives you the number of digits of n).

You can avoid the log n factor by generating combinations of n taken n - k at a time and building the number made up of the chosen n - k positions as you generate each combination (pass it as a parameter). This basically means you solve the similar problem: given n, pick n - k digits in order such that the resulting number is maximum).

Note: there is a method to solve this that does not involve brute force, but I wanted to show the OP this solution as well, since he asked how it could be brute forced in the comments. For the optimal method, investigate what would happen if we built our number digit by digit from left to right, and, for each digit d, we would remove all currently selected digits that are smaller than it. When can we remove them and when can't we?

Answer 2

In the leftmost k+1 digits, find the largest one (let us say it is located at ith location. In case there are multiple occurrences choose the leftmost one). Keep it. Repeat the algorithm for k_new = k-i+1, newNumber = i+1 to n digits of the original number.

Eg. k=5 and number = 7454982641
First k+1 digits: 745498
Best number is 9 and it is located at location i=5. 

new_k=1, new number = 82641
First k+1 digits: 82
Best number is 8 and it is located at i=1.

new_k=1, new number = 2641
First k+1 digits: 26
Best number is 6 and it is located at i=2

new_k=0, new number = 41
Answer: 98641

Complexity is O(n) where n is the size of the input number.

Edit: As iVlad mentioned, in the worst case complexity can be quadratic. You can avoid that by maintaining a heap of size at most k+1 which will increase complexity to O(nlogk).