How can I remove a certain number of digits in a number so the number obtained is minimal?

Question

How can I remove a certain number of digits in a number so the number obtained is minimal?

Specifically, I want to write a function int remove_digits(int large, int num_digits_to_remove) such that:

1. Any num_digits_to_remove digits are removed from large as though removing characters from its string representation
2. The number that is returned has the lowest possible value from removing digits as in step 1

For example, removing 4 digits from 69469813 would give 4613

I would prefer answers written in C.

Answer 1

The basic idea is that if you can only remove one digit, you want to remove the first digit (starting with the most significant digit) that is followed by a smaller digit.

For example, if your number is 123432, you want to remove the 4 (since it is followed by a 3), resulting in 12332.

You then repeat this process for as many digits as you want to remove:

char *num = "69469813";
char *buf = malloc(strlen(num)+1);
size_t to_remove = 4;

while (to_remove --> 0) {
    char *src = num;
    char *dst = buf;

    while (*src < *(src+1)) { *dst++ = *src++; } // Advance until the next digit is less than the current digit
    src++;                                       // Skip it
    while (*dst++ = *src++);                     // Copy the rest

    strcpy(num, buf);
}
printf("%s\n", num); // Prints 4613

Answer 2

Idea:

char number[] = "69469813";
char digits[ARRAY_SIZE(number)];
size_t i;

// sort digits; complexity O(n * log n);
sort_digits(digits, number);   // -> digits becomes "99866431"

for (i = 0; i < number_of_digits_to_be_removed; ++i) {
     size_t j;
     for (j = 0; j < ARRAY_SIZE(number); ++j) {
         if (number[j] == digits[i]) {
             number[j] = 'X';      // invalidate it
             break;
         }
     }
 }

 for (i = 0; i < ARRAY_SIZE(number); ++i)
     if (number[i] != 'X')
         printf("%c", number[i]);

Whole thing has a complexity of O(n * m);

Answer 3

I don't know C but here is how I would do it in java:

String original = "69469813";
String result = "";

int numNeedToBeTaken = 4;
int numLeft = original.length() - numNeedToBeTaken;

while(result.length() < numLeft)
{
    String temp = original.substring(0,original.length()-numNeedToBeTaken+1);
    int smallest= 9;
    int index = 0;
    for(int i = 0; i<temp.length(); i++)
    {
        int number = Integer.parseInt(Character.toString(temp.charAt(i)));
        if( number < smallest)
        {
            smallest = number;
            index = i+1;
        }
    }
    numNeedToBeTaken--;
    result = result.concat(String.valueOf(smallest));
    original = original.substring(index);
}
Log.d("debug","result: "+result); //tested to work with your example, returns 4613

converting this to C should be pretty easy, I only used some basic operations.