#2165

Medium

LeetCode Problem Workspace

Smallest Value of the Rearranged Number

Rearrange the digits of an integer to minimize its value while avoiding leading zeros, keeping the sign unchanged.

Problem Statement

Given an integer num, rearrange its digits such that its value is minimized, without any leading zeros. The number's sign should remain unchanged after rearranging the digits.

Return the rearranged number that results in the smallest possible value, with no leading zeros allowed for positive numbers.

Examples

Example 1

Input: num = 310

Output: 103

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

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

Solution Approach

Sorting the Digits

First, convert the integer to a string to separate the digits. For positive numbers, sort the digits in ascending order, ensuring the smallest non-zero digit is at the front. For negative numbers, sort the digits in descending order to maximize the number's negative value.

Handling Leading Zeros

For positive numbers, ensure that the smallest non-zero digit is placed at the front. If the smallest digit is zero, find the first non-zero digit and swap them. This avoids leading zeros.

Reconstruct the Number

After sorting the digits and handling the leading zeros, reconstruct the number from the sorted digits. If the number is negative, ensure that the negative sign is preserved throughout the process.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the sorting step, which is O(n log n), where n is the number of digits. The space complexity is O(n) due to the need to store the digits and handle any temporary data structures.

What Interviewers Usually Probe

Can the candidate handle edge cases like leading zeros and negative numbers effectively?
Does the candidate demonstrate an understanding of sorting algorithms?
Does the candidate efficiently minimize the number while maintaining the sign?

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle leading zeros for positive numbers.
Incorrectly handling negative numbers by failing to sort digits in descending order.
Not maintaining the sign of the number after rearranging the digits.

Follow-up variants

Handling extremely large numbers efficiently.
Modifying the solution to handle floating-point numbers with rearranged digits.
Optimizing the solution for numbers with many repeated digits.

FAQ

How do I minimize the value of a positive number's digits?

Sort the digits in ascending order, ensuring the smallest non-zero digit comes first.

How do I handle negative numbers in this problem?

For negative numbers, sort the digits in descending order to create the smallest possible negative value.

What if the number has leading zeros?

For positive numbers, rearrange the digits to place the smallest non-zero digit at the front to avoid leading zeros.

What is the primary pattern used to solve the Smallest Value of the Rearranged Number problem?

The solution combines math and sorting, focusing on minimizing the number's value while avoiding leading zeros.

How can I optimize this solution for larger numbers?

Optimizing might involve choosing efficient sorting algorithms or reducing space complexity for handling large numbers.

terminal

Solution

Solution 1: Counting

We first use an array $\textit{cnt}$ to record the number of occurrences of each digit in $\textit{num}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    def smallestNumber(self, num: int) -> int:
        neg = num < 0
        num = abs(num)
        cnt = [0] * 10
        while num:
            cnt[num % 10] += 1
            num //= 10
        ans = 0
        if neg:
            for i in reversed(range(10)):
                for _ in range(cnt[i]):
                    ans *= 10
                    ans += i
            return -ans
        if cnt[0]:
            for i in range(1, 10):
                if cnt[i]:
                    ans = i
                    cnt[i] -= 1
                    break
        for i in range(10):
            for _ in range(cnt[i]):
                ans *= 10
                ans += i
        return ans

Continue Practicing

#2160 minimum sum of four digit number after splitting digits #2195 append k integers with minimal sum #2280 minimum lines to represent a line chart