We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest Value of the Rearranged Number

Number: 2284

Difficulty: Medium

Paid? No

Companies: Microsoft, Cognizant, T-mobile

Problem Description

Given an integer num, rearrange its digits such that the resulting number is minimized and does not contain any leading zeros. Note that the sign of num remains unchanged. For positive numbers, the smallest possible arrangement is required without leading zeros. For negative numbers, rearrange the digits (ignoring the '-' sign) so that after reattaching the negative sign the overall value is minimized (i.e. the magnitude is maximized in the negative range).

Key Insights

  • For non-negative numbers, sort the digits in ascending order.
  • Handle leading zeros by placing the smallest non-zero digit at the front.
  • For negative numbers, sort the digits (from the absolute value) in descending order so that when prefixing the negative sign, the overall value becomes the smallest.
  • Separate the handling of the sign from the digit rearrangement process.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting of the digits. Space Complexity: O(n) for storing the digits.

Solution

The solution first checks the sign of the input number num. For positive numbers, convert the number to its string representation, extract and sort the digits in ascending order. To avoid leading zeros, find the first non-zero digit and swap it with the digit in the first position if necessary. For negative numbers, remove the minus sign, extract the digits, and sort them in descending order to achieve the minimal negative value upon reattaching the '-' sign. This method uses basic string manipulation, list/array sorting, and condition checking to meet the problem requirements.

Code Solutions

def smallestNumber(num):
    # If num is non-negative, sort digits in ascending order.
    if num >= 0:
        digits = list(str(num))
        # Sort digits in ascending order.
        digits.sort()
        # If the first digit is '0', find the first non-zero digit and swap.
        if digits[0] == '0':
            for i in range(1, len(digits)):
                if digits[i] != '0':
                    # Swap the first non-zero digit with the leading zero.
                    digits[0], digits[i] = digits[i], digits[0]
                    break
        # Join the digits and convert to integer.
        return int("".join(digits))
    else:
        # For negative numbers, deal with the absolute value.
        digits = list(str(-num))
        # Sort digits in descending order to get the smallest negative value.
        digits.sort(reverse=True)
        # Join the digits, convert to integer, and reapply the negative sign.
        return -int("".join(digits))

# Example usage:
print(smallestNumber(310))   # Expected output: 103
print(smallestNumber(-7605)) # Expected output: -7650
← Back to All Questions