Smallest number by rearranging digits of a given number

Find the smallest number (without leading zeros) that can be formed by rearranging the digits of a given number.

Understand the Problem

Problem Statement

Given a number, find the smallest possible number (without leading zeros) that can be formed by rearranging its digits.

The input will be a single integer N. The output should be the smallest possible number that can be formed by rearranging the digits of N, ensuring that the result does not have leading zeros.

For example, if the input is 846903, the smallest number that can be formed is 304689. If the input is 55010, the smallest number that can be formed is 10055.

Constraints

1 ≤ N ≤ 10^18 (The number can be very large, so string manipulation is recommended)
The result must not have leading zeros
The number of digits in N can be up to 18

Examples

Example 1

Input

Output

Explanation

The digits of 846903 are [8,4,6,9,0,3]. When sorted in ascending order: [0,3,4,6,8,9]. The first non-zero digit is 3, so we place it at the beginning, followed by the remaining digits including the zero: 304689.

Example 2

Input

Output

Explanation

The digits of 55010 are [5,5,0,1,0]. When sorted in ascending order: [0,0,1,5,5]. The first non-zero digit is 1, so we place it at the beginning, followed by the remaining digits including the zeros: 10055.

Solution

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

int compare(const void *a, const void *b) {
    return (*(char*)a - *(char*)b);
}

int main() {
    char num[20];
    scanf("%s", num);
    
    int len = strlen(num);
    
    // Sort the digits
    qsort(num, len, sizeof(char), compare);
    
    // Find the first non-zero digit
    int firstNonZero = 0;
    for (int i = 0; i < len; i++) {
        if (num[i] != '0') {
            firstNonZero = i;
            break;
        }
    }
    
    // Print the smallest number
    printf("%c", num[firstNonZero]);
    
    // Print the remaining digits
    for (int i = 0; i < firstNonZero; i++) {
        printf("%c", num[i]);
    }
    for (int i = firstNonZero + 1; i < len; i++) {
        printf("%c", num[i]);
    }
    
    printf("\n");
    return 0;
}

Time:O(d log d), where d is the number of digits. This is due to the sorting step using qsort().

Space:O(d) for storing the string representation of the number.

Approach:

The C solution:

Reads the input as a string to handle large numbers
Uses qsort() to sort the characters (digits) in ascending order
Finds the first non-zero digit by iterating through the sorted array
Prints the first non-zero digit at the beginning
Prints all remaining digits (including zeros) in sorted order

The key insight is that we print digits in this order: [first non-zero digit] + [all zeros] + [remaining non-zero digits in sorted order].

Visual Explanation

Loading diagram...

All Problems