Smallest Value of the Rearranged Number - Practice Coding Problems

Smallest Value of the Rearranged Number - Problem

Math Sorting Medium

You are given an integer num. Rearrange the digits of num such that its value is minimized and it does not contain any leading zeros.

Return the rearranged number with minimal value.

Note: The sign of the number does not change after rearranging the digits.

Input & Output

Example 1 — Positive Number with Zero

$ Input: num = 4320

› Output: 2034

💡 Note: Sort digits [4,3,2,0] → [0,2,3,4]. Since 0 is first, swap with first non-zero (2) → [2,0,3,4] = 2034

Example 2 — Negative Number

$ Input: num = -4320

› Output: -2034

💡 Note: Same rearrangement as positive case, but keep negative sign: -2034

Example 3 — Single Digit

$ Input: num = 0

› Output: 0

💡 Note: Single digit 0 remains 0

Constraints

-2³¹ ≤ num ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Given number with digits to rearrange

Process

Sort digits ascending, handle leading zeros

Output

Minimum possible value without leading zeros

Key Takeaway

🎯 Key Insight: Sort digits ascending for minimum value, then swap first non-zero to front to avoid leading zeros

Asked in

a Amazon 25 M Microsoft 18 G Google 15

The key insight is to sort digits in ascending order to minimize value, then handle leading zeros by swapping the first non-zero digit to the front. Best approach is sort-first with Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Handle Leading Zeros	O(n log n)	O(n)	Sort digits in ascending order, then swap first non-zero to front if needed
Generate All Permutations	O(n!)	O(n!)	Generate all possible arrangements of digits and find the minimum valid one

Sort and Handle Leading Zeros — Algorithm Steps

Extract digits and handle sign
Sort digits in ascending order
If first digit is 0, find first non-zero digit
Swap first non-zero digit to front position

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract & Sort

Convert to digits and sort ascending

Check Leading Zero

If first digit is 0, find first non-zero

Swap if Needed

Swap first non-zero to front position

Code -

solution.c — C

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

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

long long solution(long long num) {
    if (num == 0) return 0;
    
    int isNegative = num < 0;
    if (isNegative) num = -num;
    
    // Convert to digits and sort
    char digits[20];
    sprintf(digits, "%lld", num);
    int len = strlen(digits);
    qsort(digits, len, sizeof(char), compare);
    
    // Handle leading zero case
    if (digits[0] == '0') {
        // Find first non-zero digit
        for (int i = 1; i < len; i++) {
            if (digits[i] != '0') {
                // Swap with first position
                char temp = digits[0];
                digits[0] = digits[i];
                digits[i] = temp;
                break;
            }
        }
    }
    
    long long result = atoll(digits);
    return isNegative ? -result : result;
}

int main() {
    long long num;
    scanf("%lld", &num);
    printf("%lld\n", solution(num));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting the digits takes O(n log n) where n is number of digits

⚡ Linearithmic

Space Complexity

O(n)

Converting number to digit array requires O(n) space

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Handle Leading Zeros — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler