RemoveDigits

SRM 133 · 2003-02-05 · by Yarin

Class Name: RemoveDigits

Return Type: String

Method Name: maxNumber

Arg Types: (string, int)

Problem Statement

Given a non-negative integer n (n may have up to 50 digits) and another number m, remove exactly m digits from n so the remaining number is as big as possible. m will always be less than the number of digits in n.

Create a class RemoveDigits containing the method maxNumber which takes a String n and an int m and returns a String containing the biggest number when removing exactly m digits from n.

Notes

n may contain leading zeros, see example 1.
The return value should contain exactly |n|-m digits, where |n| is the number of digits in n.

Constraints

n will contain between 1 and 50 characters, inclusive.
n will only contain digits ('0'-'9').
m will be between 0 and |n|-1, inclusive, where |n| is the number of digits in n.

Examples

"834391370"
2
Returns: "8491370"

We should try to get the highest digits in the front. It's not possible to get the 9 in the front since that would require removing 4 digits, so we have to be satisfied with the 8. We still can't get the 9 to the second place in the final number, so the 4 is the highest choice for this position and thus we remove the digit 3. Now we can get the 9 as the third digit from the left in the final number by removing the second digit 3. Now we have removed 2 digits, and the number remaining is 8491370.

"0021597002943020"
3
Returns: "2597002943020"

We start with removing the two leading zeros and then the first 1, thus getting 2597002943020.

"0000500390"
2
Returns: "00500390"

"91459800928398113866079548895152924499"
22
Returns: "9999995152924499"

"98"
1
Returns: "9"

Submissions are judged against all 57 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RemoveDigits with a public method string maxNumber(string n, int m) · 57 test cases · 2 s / 256 MB per case