C language: How to find the largest number created by digits from n using string

Question

Question:Find the largest number and smallest created by digits from n (n<10 ^50) . I have tried like the below but in some cases, it's wrong

For example:

Case 1: Input 2015 Output 5210

Case 2: Input 47356359122 Output(Wrong answer) Help me please, I don't know why I got the wrong answer!!!

#include <stdio.h>
#include <string.h>

void max(char s[]) {
    int l = strlen(s);
    int i, key, j;
    for (i = 1; i < l; i++) {
        key = s[i];
        j = i - 1;
 
        while (j >= 0 && s[j] > key) {
            s[j + 1] = s[j];
            j = j - 1;
        }
        s[j + 1] = key;
    }
    s[l - 1] = '\0';
    printf("%s\n", s);
}

int main() {
    char s[100];
    fgets(s, sizeof(s), stdin);
    max(s);
}

Answer 1

Your approach is correct: sorting the digits in decreasing order produces the largest number from these digits.

Your implementation is flawed:

• you actually sort them in increasing order. You should change while (j >= 0 && s[j] > key) to

   while (j >= 0 && s[j] < key)
  

• the null terminator is set at the wrong position: you clear the last character in s. If the line read from stdin ends with a newline, this may erase it, unless the user typed a TAB character, but if the input consists only of digits, the last one will be removed. Change the code to:

   s[l - 1] = '\0';
  

Here is an alternative using counting sort:

#include <stdio.h>

void max_number(char s[]) {
    /* array to store the number of occurrences of each digit */
    int count[10] = { 0 }; 
    int i, d, c;
    /* enumerate all characters from the string, stop at the null terminator */
    for (i = 0; s[i]; i++) {
        /* only count digits from '0' to '9' */
        if (s[i] >= '0' && s[i] <= '9') {
            /* increase the digit count for this digit */
            count[s[i] - '0']++;
        }
    }
    /* output the digits from highest to lowest */
    for (i = 0, d = 10; d --> 0;) {
        for (c = count[d]; c --> 0;)
            s[i++] = '0' + d;
    }
    if (i == 0) {
       /* there were no digits in the string: store a 0 */
       s[i++] = '0';
    }
    if (s[0] == '0') {
       /* there were only zeroes in the string: keep a single 0 */
       i = 1;
    }
    /* set the null terminator */
    s[i] = '\0';
    printf("%s\n", s);
}

int main() {
    char s[100];
    if (fgets(s, sizeof(s), stdin))
        max_number(s);
    return 0;
}