Smallest Value Of The Rearranged Number - Leetcode Solution

Problem statement:

Given a non-negative integer n, rearrange the digits of n to become the smallest possible integer. Return the smallest possible integer.

Example 1:

Input: 2736 Output: 2367 Explanation: The smallest possible integer can be obtained by swapping the first and third digits, and then swapping the second and fourth digits.

Example 2:

Input: 80957 Output: 50879

Here is one possible solution to this problem:

To find the smallest rearranged number, we should put the smallest digits in the earliest positions possible. We can accomplish this by converting the digits of the input number to an array, sorting the array in ascending order, and then creating a new number from the sorted digits.

Here are the steps:

1. Convert the input integer to an array of its digits.

2. Sort the array in ascending order.

3. Create a new number from the sorted digits.

4. Return the new number.

Here's the code that implements these steps:

public int smallestNumber(int n) {
    // Convert the input integer to an array of its digits
    List<Integer> digits = new ArrayList<>();
    while (n > 0) {
        digits.add(n % 10);
        n /= 10;
    }

    // Sort the array in ascending order
    Collections.sort(digits);

    // Create a new number from the sorted digits
    int newNumber = 0;
    for (int i = digits.size() - 1; i >= 0; i--) {
        newNumber = newNumber * 10 + digits.get(i);
    }

    // Return the new number
    return newNumber;
}

This code first converts the input integer to an ArrayList of its digits using a loop that extracts the last digit of the input number by using modulo and then divides by 10 to discard the last digit. The loop continues until the input number is reduced to 0.

After this, the code sorts the ArrayList in ascending order using the Collections.sort() method, which puts the smallest digits at the start of the ArrayList.

Next, a new number is created from the sorted digits using another loop that iterates over the digits in reverse order and adds them to the new number using the formula newNumber = newNumber * 10 + digits.get(i).

Finally, the new number is returned.

This solution has a time complexity of O(n log n) due to the sorting step. However, since the input number is limited to 10^9, the actual running time is very fast and efficient.

1