Problem Description

You are given an integer num. Your task is to rearrange the digits of this number to create the smallest possible value, with the constraint that the result cannot have leading zeros.

The key requirements are:

• Rearrange the digits of the given number to minimize its value
• No leading zeros are allowed in the result (except for the number 0 itself)
• The sign of the number (positive or negative) must remain the same after rearrangement

For example:

• If num = 310, the smallest rearrangement would be 103 (not 013 since leading zeros aren't allowed)
• If num = -7605, the smallest negative number would be -7650 (arranging digits to make the largest absolute value gives the smallest negative number)

The solution uses a counting approach where it tracks the frequency of each digit (0-9) in the input number. For negative numbers, digits are arranged in descending order to maximize the absolute value (making the negative number as small as possible). For positive numbers, the smallest non-zero digit is placed first to avoid leading zeros, followed by all remaining digits in ascending order.

Intuition

To find the smallest possible number after rearranging digits, we need to think about how digit placement affects the value of a number. In any number, digits in higher positions (leftmost) contribute more to the overall value than digits in lower positions (rightmost). For instance, in the number 321, the digit 3 contributes 300, while 1 contributes only 1.

For positive numbers, we want smaller digits on the left to minimize the value. The natural approach would be to sort all digits in ascending order. However, there's a catch - we cannot have leading zeros. So if we have zeros in our number, we can't place them at the beginning. This means we need to find the smallest non-zero digit, place it first, then arrange all remaining digits (including zeros) in ascending order after it.

For negative numbers, the logic flips. To get the smallest negative number, we actually need the largest absolute value. Think about it: -9 is smaller than -1 even though 9 > 1. Therefore, for negative numbers, we want to arrange digits in descending order to maximize the absolute value, which gives us the minimum negative value.

The counting approach emerges naturally from this understanding. Instead of manipulating the digits directly, we can:

1. Count how many times each digit (0-9) appears in the original number
2. Reconstruct the number by placing digits according to our strategy:
   • For positive: smallest non-zero digit first, then all others in ascending order
   • For negative: all digits in descending order

This counting method is efficient because we only need to iterate through digits once to count them, and once more to build the result, making it a linear time solution relative to the number of digits.

Learn more about Math and Sorting patterns.

Solution Approach

The solution uses a counting sort approach with an array to track digit frequencies. Here's the step-by-step implementation:

1. Initialize and Count Digits

• Create a counting array cnt of size 10 to store the frequency of each digit (0-9)
• Determine if the number is negative and work with its absolute value
• Extract each digit using modulo operation (num % 10) and integer division (num // 10)
• Increment the count for each digit found

2. Handle Negative Numbers For negative numbers, we want the largest absolute value (to get the smallest negative):

• Traverse the cnt array from 9 down to 0 (descending order)
• For each digit i that appears cnt[i] times:
  • Multiply the answer by 10 and add the digit i
  • Repeat this cnt[i] times
• Return the negative of the constructed number

3. Handle Positive Numbers For positive numbers, we need to avoid leading zeros:

• First, check if there are any zeros (cnt[0] > 0)
• If zeros exist, find the smallest non-zero digit:
  • Iterate from 1 to 9 to find the first digit with cnt[i] > 0
  • Set this as the starting digit of our answer
  • Decrement its count by 1
• Then arrange all remaining digits in ascending order:
  • Traverse from 0 to 9
  • For each digit i that appears cnt[i] times:
    • Multiply the answer by 10 and add the digit i
    • Repeat this cnt[i] times

4. Build the Result The number is constructed digit by digit using the formula: ans = ans * 10 + digit. This effectively shifts existing digits left and adds the new digit at the rightmost position.

The time complexity is O(d) where d is the number of digits, and space complexity is O(1) since the counting array has a fixed size of 10.

Example Walkthrough

Let's walk through the solution with num = 310:

Step 1: Initialize and Count Digits

• Create counting array cnt = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
• Number is positive, so we'll use positive number logic
• Extract digits:
  • 310 % 10 = 0, so cnt[0]++, now cnt = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0], num becomes 31
  • 31 % 10 = 1, so cnt[1]++, now cnt = [1, 1, 0, 0, 0, 0, 0, 0, 0, 0], num becomes 3
  • 3 % 10 = 3, so cnt[3]++, now cnt = [1, 1, 0, 1, 0, 0, 0, 0, 0, 0], num becomes 0

Step 2: Handle Positive Number with Leading Zero Prevention

• Check if zeros exist: cnt[0] = 1, so yes
• Find smallest non-zero digit:
  • Check cnt[1] = 1 > 0, found it!
  • Start answer with 1: ans = 1
  • Decrement cnt[1] to 0: cnt = [1, 0, 0, 1, 0, 0, 0, 0, 0, 0]

Step 3: Add Remaining Digits in Ascending Order

• Traverse cnt from index 0 to 9:
  • cnt[0] = 1: Add one 0: ans = 1 * 10 + 0 = 10
  • cnt[1] = 0: Skip
  • cnt[2] = 0: Skip
  • cnt[3] = 1: Add one 3: ans = 10 * 10 + 3 = 103
  • cnt[4] through cnt[9] = 0: Skip all

Result: 103

Now let's trace through a negative example with num = -7605:

Step 1: Count Digits

• Working with absolute value 7605
• After counting: cnt = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0] (one 0, one 5, one 6, one 7)

Step 2: Handle Negative Number (Descending Order)

• Start from digit 9 down to 0:
  • cnt[9] = 0: Skip
  • cnt[8] = 0: Skip
  • cnt[7] = 1: Add one 7: ans = 0 * 10 + 7 = 7
  • cnt[6] = 1: Add one 6: ans = 7 * 10 + 6 = 76
  • cnt[5] = 1: Add one 5: ans = 76 * 10 + 5 = 765
  • cnt[4] through cnt[1] = 0: Skip all
  • cnt[0] = 1: Add one 0: ans = 765 * 10 + 0 = 7650

Step 3: Apply Negative Sign

• Return -7650

Result: -7650

Solution Implementation

Time and Space Complexity

The time complexity is O(log n), where n is the absolute value of the input number num. This is because:

• The first while loop extracts digits by repeatedly dividing by 10, which takes O(log n) iterations (the number of digits in n)
• The reconstruction loops iterate through the fixed array of size 10, and for each position, iterate based on the count of that digit. The total iterations across all digits equals the number of digits in the original number, which is O(log n)

The space complexity is O(1). The algorithm uses:

• A fixed-size array cnt of length 10 to store digit counts
• A few constant variables (neg, num, ans, i)
• Since the array size is constant (always 10) regardless of input size, the space usage remains constant

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling the Special Case of Zero

One of the most common pitfalls is forgetting that when the input is 0, the function should return 0 directly. The current implementation handles this correctly because when num = 0, the while loop doesn't execute (since 0 > 0 is false), leaving all digit counts at 0, and the result naturally becomes 0.

Problem Example:

# If not handled properly, num = 0 might cause issues
# Some implementations might try to extract digits and fail

Solution: Add an explicit check at the beginning:

if num == 0:
    return 0

2. Integer Overflow for Large Numbers

When building the result by repeatedly multiplying by 10 and adding digits, very large numbers might cause integer overflow in languages with fixed integer sizes. Python handles arbitrary precision integers, but this could be an issue in other languages.

Problem Example:

# For very large numbers like 9999999999999999
# In languages like Java/C++, this could overflow

Solution: In Python, this isn't an issue, but in other languages, consider using long integers or checking for overflow:

# Check if result will overflow before multiplication
if result > (2**31 - 1) // 10:
    # Handle overflow case
    pass

3. Incorrectly Handling Negative Numbers with Leading Zeros After Rearrangement

A subtle pitfall occurs when dealing with negative numbers that have zeros. The algorithm must ensure zeros are placed optimally to minimize the absolute value.

Problem Example:

# For num = -7605
# Incorrect: -0567 (invalid) or -5067 (not optimal)
# Correct: -7650 (largest absolute value = smallest negative)

Solution: The current implementation handles this correctly by arranging digits in descending order for negative numbers, which naturally places zeros at the end.

4. Forgetting to Restore the Sign

After processing the absolute value, forgetting to restore the negative sign is a common mistake.

Problem Example:

# Processing num = -321
# Forgetting to add back the negative sign would return 123 instead of -321

Solution: Always remember to negate the result for negative inputs:

if is_negative:
    return -result  # Don't forget the negative sign!

5. Edge Case: All Zeros Except One Non-Zero Digit

When a positive number consists of mostly zeros with just one non-zero digit, ensuring proper placement is crucial.

Problem Example:

# For num = 1000
# Incorrect: 0001 (leading zeros not allowed)
# Correct: 1000

Solution: The algorithm correctly handles this by:

1. Finding the smallest non-zero digit first
2. Placing it at the beginning
3. Then appending all zeros

This ensures no leading zeros while maintaining the smallest possible value.