# Smallest Value of the Rearranged Number
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/smallest-value-of-the-rearranged-number)
Canonical: https://scaleengineer.com/dsa/problems/smallest-value-of-the-rearranged-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Companies:** [Cognizant](https://scaleengineer.com/companies/cognizant)
---
## Problem
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 that the sign of the number does not change after rearranging the digits.

**Example 1:**

**Input:** num = 310
**Output:** 103
**Explanation:** The possible arrangements for the digits of 310 are 013, 031, 103, 130, 301, 310. 
The arrangement with the smallest value that does not contain any leading zeros is 103.

**Example 2:**

**Input:** num = -7605
**Output:** -7650
**Explanation:** Some possible arrangements for the digits of -7605 are -7650, -6705, -5076, -0567.
The arrangement with the smallest value that does not contain any leading zeros is -7650.

**Constraints:**

* `-1015 <= num <= 1015`

# Approaches
## Sorting Digits as Characters
This approach treats the number as a sequence of characters (digits). We can convert the number to a string, sort its characters, and then reconstruct the number. The logic differs slightly for positive and negative numbers to ensure the result is the smallest possible value.
**Time:** O(d log d), where `d` is the number of digits in `num`. The dominant operation is sorting the character array. `d` is approximately `log10(num)`. · **Space:** O(d), where `d` is the number of digits in `num`. We need space to store the character array of digits.
**Pros:** Relatively simple to understand and implement using standard library functions.; Handles all cases correctly.
**Cons:** Slightly less efficient than a counting-based approach because general-purpose sorting (`O(d log d)`) is used where a linear time sort (`O(d)`) is possible.
### Explanation
The core idea is to rearrange digits, and sorting is a natural way to do this. The logic depends on the sign of the input number `num`.

- **Positive `num`**: To get the smallest number, we need to arrange the digits in non-decreasing (ascending) order. For example, for `310`, the digits are `3, 1, 0`. Sorting them gives `0, 1, 3`. However, the result cannot have leading zeros. So, we must find the first non-zero digit in the sorted sequence (`1` in this case) and swap it with the first digit (`0`). This gives `1, 0, 3`, and the number `103`.

- **Negative `num`**: To get the smallest negative number (e.g., `-50` is smaller than `-5`), we need to make its absolute value as large as possible. This is achieved by arranging the digits in non-increasing (descending) order. For `-7605`, the digits `7, 6, 0, 5` arranged in descending order form `7650`. The final result is `-7650`.

The implementation involves converting the number to a character array, sorting it, and then building the result string based on the logic above.

```java
import java.util.Arrays;

class Solution {
    public long smallestNumber(long num) {
        if (num == 0) {
            return 0;
        }

        boolean isNegative = num < 0;
        // Work with the absolute value
        long absNum = Math.abs(num);
        char[] digits = String.valueOf(absNum).toCharArray();
        
        // Sort digits in ascending order
        Arrays.sort(digits);

        if (isNegative) {
            // For negative numbers, we want the largest absolute value.
            // This is achieved by arranging digits in descending order.
            // We can sort ascending and then reverse the resulting string.
            StringBuilder sb = new StringBuilder(new String(digits));
            sb.reverse();
            return -Long.parseLong(sb.toString());
        } else {
            // For positive numbers, we want the smallest value.
            // This is achieved by arranging digits in ascending order,
            // but with no leading zeros.
            if (digits[0] == '0') {
                // Find the first non-zero digit
                int firstNonZeroIndex = 0;
                for (int i = 0; i < digits.length; i++) {
                    if (digits[i] != '0') {
                        firstNonZeroIndex = i;
                        break;
                    }
                }
                // Swap the first digit with the first non-zero digit
                char temp = digits[0];
                digits[0] = digits[firstNonZeroIndex];
                digits[firstNonZeroIndex] = temp;
            }
            return Long.parseLong(new String(digits));
        }
    }
}
```
### Algorithm
*   Handle the edge case `num = 0`. If so, return `0`.
*   Determine the sign of `num`. Store it in a boolean variable, e.g., `isNegative`.
*   Work with the absolute value of `num`. Convert `abs(num)` to a string, and then to a character array `chars`.
*   Sort the character array `chars` in ascending order.
*   **If the original number was positive (`!isNegative`):**
    *   If the first character `chars[0]` is '0', find the first index `i` where `chars[i] != '0'`.
    *   Swap `chars[0]` and `chars[i]`.
    *   Convert the modified character array back to a string and then parse it to a `long`.
*   **If the original number was negative (`isNegative`):**
    *   Build a string from the sorted array and then reverse it.
    *   Parse the reversed string to a `long` and multiply by -1 to restore the sign.
*   Return the resulting `long`.

## Digit Counting and Reconstruction
This approach is a more optimized version that avoids general-purpose sorting. Since the digits are limited (0-9), we can use a counting sort algorithm. We count the frequency of each digit and then reconstruct the number string based on these counts, which is more efficient.
**Time:** O(d), where `d` is the number of digits in `num`. Populating the `counts` array and reconstructing the string both take `O(d)` time. · **Space:** O(d), where `d` is the number of digits. The `counts` array takes constant space `O(1)`. The `StringBuilder` and the initial string conversion take `O(d)` space.
**Pros:** Most efficient approach with linear time complexity.; Avoids the overhead of a general-purpose sorting algorithm.
**Cons:** The logic for reconstructing the number is slightly more complex than the sorting approach, especially for the positive case with leading zeros.
### Explanation
This approach optimizes the sorting step. Since the elements to be sorted are always digits from 0 to 9, we can use a linear-time sorting algorithm called Counting Sort.

First, we count the frequency of each digit in the input number and store it in an array of size 10. Then, we reconstruct the number by building a string.

- **Positive `num`**: To form the smallest number, we must place the smallest non-zero digit first to avoid a leading zero. We find the smallest digit from 1 to 9 that appeared in the number, append it to our result, and decrement its count. After that, we append all the zeros. Finally, we append the remaining digits (1-9) in ascending order.

- **Negative `num`**: To form the smallest negative number, we need the largest absolute value. We construct this by appending digits in descending order (from 9 down to 0) according to their frequencies.

This method is more efficient as it processes the digits in linear time.

```java
class Solution {
    public long smallestNumber(long num) {
        if (num == 0) {
            return 0;
        }

        boolean isNegative = num < 0;
        long absNum = Math.abs(num);

        // Count frequency of each digit
        int[] counts = new int[10];
        String s = String.valueOf(absNum);
        for (char c : s.toCharArray()) {
            counts[c - '0']++;
        }

        StringBuilder sb = new StringBuilder();
        if (isNegative) {
            // Build the largest number for the absolute value (descending order)
            for (int i = 9; i >= 0; i--) {
                for (int j = 0; j < counts[i]; j++) {
                    sb.append(i);
                }
            }
            return -Long.parseLong(sb.toString());
        } else {
            // Build the smallest number (ascending order, no leading zero)
            // 1. Append the smallest non-zero digit
            for (int i = 1; i <= 9; i++) {
                if (counts[i] > 0) {
                    sb.append(i);
                    counts[i]--;
                    break;
                }
            }
            // 2. Append remaining digits
            for (int i = 0; i <= 9; i++) {
                for (int j = 0; j < counts[i]; j++) {
                    sb.append(i);
                }
            }
            return Long.parseLong(sb.toString());
        }
    }
}
```
### Algorithm
*   Handle the edge case `num = 0`. If so, return `0`.
*   Determine the sign of `num` and work with `abs(num)`.
*   Create an integer array `counts` of size 10, initialized to zeros.
*   Populate the `counts` array by iterating through the digits of `abs(num)`.
*   Use a `StringBuilder` to construct the result string.
*   **If the original number was positive:**
    *   Find the smallest digit `d` from 1 to 9 with a positive count. Append `d` to the `StringBuilder` and decrement its count.
    *   Append '0' `counts[0]` times.
    *   Append the remaining digits (1-9) in ascending order based on their counts.
*   **If the original number was negative:**
    *   Iterate from `d = 9` down to 0. For each digit, append it `counts[d]` times.
*   Convert the `StringBuilder` to a string, parse it to a `long`, and apply the original sign.
*   Return the result.

# Solutions
### Java

```java
class Solution {
public
  long smallestNumber(long num) {
    if (num == 0) {
      return 0;
    }
    int[] cnt = new int[10];
    boolean neg = num < 0;
    num = Math.abs(num);
    while (num != 0) {
      cnt[(int)(num % 10)]++;
      num /= 10;
    }
    long ans = 0;
    if (neg) {
      for (int i = 9; i >= 0; --i) {
        while (cnt[i]-- > 0) {
          ans = ans * 10 + i;
        }
      }
      return -ans;
    }
    if (cnt[0] > 0) {
      for (int i = 1; i < 10; ++i) {
        if (cnt[i] > 0) {
          ans = ans * 10 + i;
          cnt[i]--;
          break;
        }
      }
    }
    for (int i = 0; i < 10; ++i) {
      while (cnt[i]-- > 0) {
        ans = ans * 10 + i;
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number} num * @return {number} */ var smallestNumber = function ( num ) { const neg = num < 0 ; num = Math . abs ( num ); const cnt = Array ( 10 ). fill ( 0 ); while ( num > 0 ) { cnt [ num % 10 ] ++ ; num = Math . floor ( num / 10 ); } let ans = 0 ; if ( neg ) { for ( let i = 9 ; i >= 0 ; i -- ) { while ( cnt [ i ] > 0 ) { ans = ans * 10 + i ; cnt [ i ] -- ; } } return - ans ; } if ( cnt [ 0 ] > 0 ) { for ( let i = 1 ; i < 10 ; i ++ ) { if ( cnt [ i ] > 0 ) { cnt [ i ] -- ; ans = i ; break ; } } } for ( let i = 0 ; i < 10 ; i ++ ) { while ( cnt [ i ] > 0 ) { ans = ans * 10 + i ; cnt [ i ] -- ; } } return ans ; };
```

### CPP

```cpp
class Solution {
public:
  long long smallestNumber(long long num) {
    if (num == 0)
      return 0;
    vector<int> cnt(10);
    bool neg = num < 0;
    num = abs(num);
    while (num) {
      cnt[num % 10]++;
      num /= 10;
    }
    long long ans = 0;
    if (neg) {
      for (int i = 9; i >= 0; --i)
        while (cnt[i]--)
          ans = ans * 10 + i;
      return -ans;
    }
    if (cnt[0]) {
      for (int i = 1; i < 10; ++i) {
        if (cnt[i]) {
          ans = ans * 10 + i;
          cnt[i]--;
          break;
        }
      }
    }
    for (int i = 0; i < 10; ++i)
      while (cnt[i]--)
        ans = ans * 10 + i;
    return ans;
  }
};

```

### Python

```python
class Solution:
    def smallestNumber(self, num: int) -> int: if num == 0: return 0 cnt = [0] * 10 neg = num < 0 num = abs(num) while num: num, v = divmod(num, 10) cnt[v] += 1 ans = "" if neg: for i in range(9, - 1, - 1): if cnt[i]: ans += str(i) * cnt[i] return - int(ans) if cnt[0]: for i in range(1, 10): if cnt[i]: ans += str(i) cnt[i] -= 1 break for i in range(10): if cnt[i]: ans += str(i) * cnt[i] return int(ans)

```