CODEWITHSUNDEEP
cmindigit
boa_in_samoa
boa_in_samoa

Reputation: 607

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

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.

Upvotes: 3

Views: 3583

Answers (3)

rockhyrax
rockhyrax

Reputation: 34

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

Upvotes: 1

what is sleep
what is sleep

Reputation: 905

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.

Upvotes: -1

ensc
ensc

Reputation: 6984

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);

Upvotes: 3

Related Questions