2165. Smallest Value of the Rearranged Number #

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:

• 10^15 <= num <= 10^15

Problem Summary #

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

Return the rearranged number without leading zeros and with the smallest value. Note that after rearranging the digits, the sign of num does not change.

Solution Ideas #

• First count the number of occurrences of each digit. Then sort the digits in ascending order. If the original number is positive, when digit 0 appears, first place the second smallest digit at the first position, then place all the 0s. Then continue placing the second smallest, the third smallest, and so on.
• If the original number is negative, arrange the digits in reverse order, that is, place the largest digit first, then the next largest digit, until the smallest digit is placed. Because the larger the number is, the smaller its corresponding negative number is.

Code #

package leetcode

import "sort"

func smallestNumber(num int64) int64 {
	pos := true
	if num < 0 {
		pos = false
		num *= -1
	}
	nums, m, res := []int{}, map[int]int{}, 0
	for num != 0 {
		tmp := int(num % 10)
		m[tmp]++
		num = num / 10
	}

	for k := range m {
		nums = append(nums, k)
	}
	if pos {
		sort.Ints(nums)
	} else {
		sort.Sort(sort.Reverse(sort.IntSlice(nums)))
	}

	if nums[0] == 0 && len(nums) > 1 {
		res += nums[1]
		m[nums[1]]--
	}

	for _, v := range nums {
		if res != 0 {
			for j := m[v]; j > 0; j-- {
				res = res * 10
				res += v
			}
		} else {
			res += v
			tmp := m[v] - 1
			for j := tmp; j > 0; j-- {
				res = res * 10
				res += v
			}
		}
	}
	if !pos {
		return -1 * int64(res)
	}
	return int64(res)
}