CODEWITHSUNDEEP
algorithmdynamic-programminggreedy
NPK
NPK

Reputation: 123

Find the maximum K digit number formed by a given number while preserving the order

Given a number, we have to find the maximum 'K' digit number while preserving the order ( 'K' digit number will be a subsequence ).

Input : The number 'n' and number of digits you should pick up to form the answer 'K'
Output : The maximum formed K digit number

Example : 

Input : n = 912583, k=3
Output : 983

Upvotes: 1

Views: 2019

Answers (4)

anv
anv

Reputation: 1

I stumbled upon this (this forms part of the solution) while solving https://leetcode.com/problems/create-maximum-number/description/ As Matt pointed in his answer, a greedy strategy is good enough. Here is complete C++ program with a driver. n = 78859 and k = 3 outputs 889

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

template <typename IIT, typename OIT>
void
MaxNumPreservingOrder(IIT first, IIT last, OIT output, int k) {
    if (k == 0)
        return;
    auto N = distance(first, last);
    if (N == k) {
        copy(first, last, output);
        return;
    }
    auto it = first;
    while (k > 0)  {
        auto maxval = *max_element(it, last - k + 1);
        it = find(it, last - k + 1, maxval);
        *output = *it;
        ++output;
        ++it;
        --k;
    }
    return;
}

int
main(void) {
    vector< int > v = {7, 8, 8, 5, 9}, o;
    int k = 3;
    o.reserve(k);
    MaxNumPreservingOrder(begin(v), end(v), back_inserter(o), k);
    copy(begin(o), end(o), ostream_iterator< int >(cout, " "));
    cout << "\n";
    return 0;
}

Upvotes: 0

notbad
notbad

Reputation: 2877

It can be solved by dynamic programming. You need the state dp[i][j], which is the optimal value when you choose j digits from the first i-1 digits. Then you can solve it:

void solve(int n, int k) {
    string str = string(n);
    int dp[32][32];
    memset(dp, 0, sizeof(dp));
    for (size_t i = 0; i < str.length(); ++i) {
        dp[i + 1][1] = max(dp[i][1], str[i] - '0');
        for (size_t j = 2; j <= k; ++j) {
            dp[i + 1][j] = max(dp[i][j - 1] * 10 + str[i] - '0', dp[i][j]);
        }
    }

    cout << dp[str.length][k];
}

Upvotes: 0

Kevin
Kevin

Reputation: 551

Here's my solution just so that there is a code answer here (I found the question interesting enough to work it out). Basically I just find the first largest digit that still has enough trailing numbers to fill out the requisite length, and then repeats the problem recursively for the substring after that first largest digit (basically what Matt Timmermans suggested). I tested this a bit so I think it is complete and doesn't have any glaring bugs, but I may definitely have missed an edge case.

I realize that this is probably not the fastest I could make this algorithm since I am doing a lot of variable casting from int to string and back, but since it is a relatively small input size I figured I wouldn't worry about it unless someone wants me to.

Note: It returns 0 in cases where the inputs don't make sense like if the requested length is longer than the input.

private int GetMaximumNumber(int input, int length)
{
    input = Math.Abs(input);
    var maximumNumber = 0;
    var inputString = input.ToString();
    if (length > inputString.Length || length < 1)
        return maximumNumber;

    var indexOfMaxDigit = FindMaximumDigit(input, length);

    var maxDigit = int.Parse(inputString.Substring(indexOfMaxDigit, 1));
    if (length > 1)
        maximumNumber = (maxDigit * (int)(Math.Pow(10.0, (double)length-1))) + GetMaximumNumber(int.Parse(inputString.Substring(indexOfMaxDigit + 1)), length - 1);
    else
        maximumNumber = maxDigit;

    return maximumNumber;
}

private int FindMaximumDigit(int input, int length)
{
    var indexOfMaxDigit = -1;
    var inputSubstring = input.ToString().Substring(0, input.ToString().Length - length + 1);
    for (var i = 9; i > -1; i--)
    {
        indexOfMaxDigit = inputSubstring.IndexOf(i.ToString(), StringComparison.Ordinal);
        if (indexOfMaxDigit != -1)
            break;
    }

    return indexOfMaxDigit;
}

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59154

You don't actually need dynamic programming to solve this problem. The largest K-digit number will always start with the largest possible digit, and it's always best to choose the earliest possible occurrence of the largest possible digit, because that leaves the most options open for the remaining digits.

Similarly, the best second digit is the earliest occurrence of the largest possible second digit, etc., until you're done.

Dynamic programming is used when the locally best choice (like earliest occurrence of the largest possible digit) isn't always the globally best choice.

Upvotes: 2

Related Questions