[Question] Least Number After Deleting Digits

Question

Please get the least number after deleting k digits from the input number.

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

Analysis

There’s a solution which instead of ‘delete k’, find the smallest number by ‘keeping (n-k) numbers’. It’s more strightforward.

Solution

1. From the start, search till the end.
1. If a digit is greater than next one, delete it.
2. If all digits are increasingly sorted, delete last.
2. Each time go back to start to search again.

Example

24635 -> 2435 -> 235 -> 23

Code

from Harry He

``````public static String getLeastNumberDeletingDigits_1(String number, int k) {
String leastNumber = number;
while(k > 0 && leastNumber.length() > 0) {
int firstDecreasingDigit = getFirstDecreasing(leastNumber);
if(firstDecreasingDigit >= 0) {
leastNumber = removeDigit(leastNumber, firstDecreasingDigit);
}
else {
leastNumber = removeDigit(leastNumber, leastNumber.length() - 1);
}

--k;
}

return leastNumber;
}

private static int getFirstDecreasing(String number) {
for(int i = 0; i < number.length() - 1; ++i) {
int curDigit = number.charAt(i) - '0';
int nextDigit = number.charAt(i + 1) - '0';
if(curDigit > nextDigit) {
return i;
}
}

return -1;
}

private static String removeDigit(String number, int digitIndex) {
String result = "";
if(digitIndex > 0) {
result = number.substring(0, digitIndex);
}
if(digitIndex < number.length() - 1) {
result += number.substring(digitIndex + 1);
}

return result;
}
``````
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://www.shuati123.com/blog/2014/07/23/Least-Number-after-Deleting-Digits/", "fetch_time": 1516652676000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2018-05/segments/1516084891539.71/warc/CC-MAIN-20180122193259-20180122213259-00710.warc.gz", "warc_record_offset": 540777452, "warc_record_length": 3924, "token_count": 410, "char_count": 1544, "score": 3.765625, "int_score": 4, "crawl": "CC-MAIN-2018-05", "snapshot_type": "latest", "language": "en", "language_score": 0.5081155300140381, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00048-of-00064.parquet"}