Jobs

Interviews

Discussions

Smallest Value of the Rearranged Number

Medium

Asked by:

23 views

Topics:

ArraysGreedy Algorithms

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¹⁵ <= num <= 10¹⁵

Try coding it in LeetCode

Smallest Value of the Rearranged Number

Medium

Asked by:

23 views

Topics:

ArraysGreedy Algorithms

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¹⁵ <= num <= 10¹⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input number be negative, positive, or zero?
What is the range of the input number? Is there a practical upper limit I should be aware of?
If the input is zero, should I return zero or is there a specific rearrangement expected?
What data type should I return the rearranged number as (e.g., string, long)?
Should leading zeros be removed from the rearranged number, and if so, how should I handle a number consisting only of zeros?

Brute Force Solution

Approach

The brute force way to find the smallest rearranged number is to try every single possible arrangement of its digits. We generate all possible numbers and then pick the smallest one that doesn't have leading zeros (unless the original number was zero).

Here's how the algorithm would work step-by-step:

First, find all the different ways you can order the digits of the given number.
This means trying every possible combination of the digits, like shuffling a deck of cards and writing down each order.
For each arrangement, check if it's a valid number: it shouldn't have a leading zero unless all digits are zero.
If it's a valid number, save it.
After you've tried all the possible arrangements and saved the valid ones, find the smallest number among those you saved.

Code Implementation

from itertools import permutations

def find_smallest_rearranged_number_brute_force(number):
    number_string = str(number)
    digits = list(number_string)
    all_permutations = permutations(digits)
    smallest_number = float('inf')
    
    for permutation in all_permutations:
        arranged_number_string = "".join(permutation)
        
        # Check for leading zeros, this step ensures a valid number
        if len(arranged_number_string) > 1 and arranged_number_string[0] == '0':
            continue
        
        arranged_number = int(arranged_number_string)
        
        # Need to handle the edge case of the original number being zero
        if number == 0:
            smallest_number = 0
            break

        #Find the absolute smallest valid permutation
        smallest_number = min(smallest_number, arranged_number)

    if smallest_number == float('inf'):
        return 0
    else:
        return smallest_number

Big(O) Analysis

Time Complexity

O(n!) – The brute force approach involves generating all possible permutations of the digits of the input number. If the number has n digits, there are n! (n factorial) possible permutations. After generating each permutation, we check if it has leading zeros, which takes O(n) time in the worst case. Then, we find the minimum valid permutation among all the generated ones, which takes O(n!) in the worst case. Therefore, the dominant factor is generating n! permutations, making the overall time complexity O(n!).

Space Complexity

O(N!) – The algorithm generates all possible permutations of the input number's digits. The number of permutations for a number with N digits is N! For each permutation, we store it in memory before checking for leading zeros and storing it for later comparison. Therefore, in the worst case, we might store a collection of N! numbers, each having at most N digits. Since storing a single number with N digits will only add O(N) space, we are still dominated by the number of possible permutations of the digits, which is N!. This leads to a space complexity of O(N!).

Optimal Solution

Approach

The key is to arrange the digits to form the smallest possible number while avoiding leading zeros. We'll handle positive and negative numbers differently, focusing on placing the smallest non-zero digit first for positive numbers and the largest digit (closest to zero) after the negative sign for negative numbers.

Here's how the algorithm would work step-by-step:

First, determine if the number is positive or negative.
If the number is positive, count how many times each digit (0-9) appears.
Find the smallest digit that's not zero. Place it as the first digit of the result.
Add all the zeros after that smallest digit. This avoids leading zeros and puts them in the best spot to minimize the number's value.
Add the remaining digits in increasing order after the zeros.
If the number is negative, make it positive and then count how many times each digit appears.
Place the negative sign first.
Find the largest digit and place it after the negative sign. This is because for negative numbers, you want to be as close to 0 as possible.
Add the remaining digits in decreasing order after the largest digit.

Code Implementation

def find_smallest_rearranged_number(number):
    is_negative = number < 0
    number = abs(number)
    digit_counts = [0] * 10
    for digit_char in str(number):
        digit = int(digit_char)
        digit_counts[digit] += 1

    if is_negative:
        result = "-"

        # Negative number: find largest digit to put after '-'
        for digit in range(9, -1, -1):
            if digit_counts[digit] > 0:
                result += str(digit)
                digit_counts[digit] -= 1
                break

        # Append remaining digits in decreasing order
        for digit in range(9, -1, -1):
            result += str(digit) * digit_counts[digit]
        return int(result)
    else:
        # Positive number: find smallest non-zero digit
        for digit in range(1, 10):
            if digit_counts[digit] > 0:
                result = str(digit)
                digit_counts[digit] -= 1
                break

        #Append the zeros to minimize value.
        result += "0" * digit_counts[0]

        # Append remaining digits in increasing order
        for digit in range(1, 10):
            result += str(digit) * digit_counts[digit]
        return int(result)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the digits of the input number once to count the frequency of each digit. For a positive number, it finds the smallest non-zero digit and then appends zeros and the remaining digits. For a negative number, it finds the largest digit and appends the remaining digits. The digit counting takes O(n) time where n is the number of digits. The process of appending the digits also takes O(n) time at most. Therefore, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm uses a fixed-size array (or hash map) of size 10 to count the occurrences of each digit (0-9). The size of this array is independent of the input number's magnitude or number of digits. Therefore, the auxiliary space used remains constant regardless of the input, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Input is zero	Return 0 directly, as there's nothing to rearrange.
Input is a single digit number	Return the number itself since no rearrangement is needed.
Input contains leading zeros after rearrangement	Ensure the first non-zero digit is placed at the beginning of the number.
Input is a negative number	Handle the negative sign separately and find the largest value of the remaining digits (instead of smallest).
Input is close to the maximum or minimum integer value	Be wary of integer overflow when rearranging and converting back to an integer.
Input has many zeros	Ensure that zeros are placed after the first non-zero digit.
Input contains both positive and negative digits (treated as string)	This is an invalid input - the prompt specifies an integer input, so either throw an exception or return an error value.
All digits are the same	Arrange the digits in ascending order which will result in the number itself.

Input is zero

How to Handle:

Return 0 directly, as there's nothing to rearrange.

Input is a single digit number

How to Handle:

Return the number itself since no rearrangement is needed.

Input contains leading zeros after rearrangement

How to Handle:

Ensure the first non-zero digit is placed at the beginning of the number.

Input is a negative number

How to Handle:

Handle the negative sign separately and find the largest value of the remaining digits (instead of smallest).

Input is close to the maximum or minimum integer value

How to Handle:

Be wary of integer overflow when rearranging and converting back to an integer.

Input has many zeros

How to Handle:

Ensure that zeros are placed after the first non-zero digit.

Input contains both positive and negative digits (treated as string)

How to Handle:

This is an invalid input - the prompt specifies an integer input, so either throw an exception or return an error value.

All digits are the same

How to Handle:

Arrange the digits in ascending order which will result in the number itself.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input number be negative, positive, or zero?
What is the range of the input number? Is there a practical upper limit I should be aware of?
If the input is zero, should I return zero or is there a specific rearrangement expected?
What data type should I return the rearranged number as (e.g., string, long)?
Should leading zeros be removed from the rearranged number, and if so, how should I handle a number consisting only of zeros?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, find all the different ways you can order the digits of the given number.
This means trying every possible combination of the digits, like shuffling a deck of cards and writing down each order.
For each arrangement, check if it's a valid number: it shouldn't have a leading zero unless all digits are zero.
If it's a valid number, save it.
After you've tried all the possible arrangements and saved the valid ones, find the smallest number among those you saved.

Code Implementation

from itertools import permutations

def find_smallest_rearranged_number_brute_force(number):
    number_string = str(number)
    digits = list(number_string)
    all_permutations = permutations(digits)
    smallest_number = float('inf')
    
    for permutation in all_permutations:
        arranged_number_string = "".join(permutation)
        
        # Check for leading zeros, this step ensures a valid number
        if len(arranged_number_string) > 1 and arranged_number_string[0] == '0':
            continue
        
        arranged_number = int(arranged_number_string)
        
        # Need to handle the edge case of the original number being zero
        if number == 0:
            smallest_number = 0
            break

        #Find the absolute smallest valid permutation
        smallest_number = min(smallest_number, arranged_number)

    if smallest_number == float('inf'):
        return 0
    else:
        return smallest_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, determine if the number is positive or negative.
If the number is positive, count how many times each digit (0-9) appears.
Find the smallest digit that's not zero. Place it as the first digit of the result.
Add all the zeros after that smallest digit. This avoids leading zeros and puts them in the best spot to minimize the number's value.
Add the remaining digits in increasing order after the zeros.
If the number is negative, make it positive and then count how many times each digit appears.
Place the negative sign first.
Find the largest digit and place it after the negative sign. This is because for negative numbers, you want to be as close to 0 as possible.
Add the remaining digits in decreasing order after the largest digit.

Code Implementation

def find_smallest_rearranged_number(number):
    is_negative = number < 0
    number = abs(number)
    digit_counts = [0] * 10
    for digit_char in str(number):
        digit = int(digit_char)
        digit_counts[digit] += 1

    if is_negative:
        result = "-"

        # Negative number: find largest digit to put after '-'
        for digit in range(9, -1, -1):
            if digit_counts[digit] > 0:
                result += str(digit)
                digit_counts[digit] -= 1
                break

        # Append remaining digits in decreasing order
        for digit in range(9, -1, -1):
            result += str(digit) * digit_counts[digit]
        return int(result)
    else:
        # Positive number: find smallest non-zero digit
        for digit in range(1, 10):
            if digit_counts[digit] > 0:
                result = str(digit)
                digit_counts[digit] -= 1
                break

        #Append the zeros to minimize value.
        result += "0" * digit_counts[0]

        # Append remaining digits in increasing order
        for digit in range(1, 10):
            result += str(digit) * digit_counts[digit]
        return int(result)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is zero	Return 0 directly, as there's nothing to rearrange.
Input is a single digit number	Return the number itself since no rearrangement is needed.
Input contains leading zeros after rearrangement	Ensure the first non-zero digit is placed at the beginning of the number.
Input is a negative number	Handle the negative sign separately and find the largest value of the remaining digits (instead of smallest).
Input is close to the maximum or minimum integer value	Be wary of integer overflow when rearranging and converting back to an integer.
Input has many zeros	Ensure that zeros are placed after the first non-zero digit.
Input contains both positive and negative digits (treated as string)	This is an invalid input - the prompt specifies an integer input, so either throw an exception or return an error value.
All digits are the same	Arrange the digits in ascending order which will result in the number itself.

Input is zero

How to Handle:

Return 0 directly, as there's nothing to rearrange.

Input is a single digit number

How to Handle:

Return the number itself since no rearrangement is needed.

Input contains leading zeros after rearrangement

How to Handle:

Ensure the first non-zero digit is placed at the beginning of the number.

Input is a negative number

How to Handle:

Handle the negative sign separately and find the largest value of the remaining digits (instead of smallest).

Input is close to the maximum or minimum integer value

How to Handle:

Be wary of integer overflow when rearranging and converting back to an integer.

Input has many zeros

How to Handle:

Ensure that zeros are placed after the first non-zero digit.

Input contains both positive and negative digits (treated as string)

How to Handle:

This is an invalid input - the prompt specifies an integer input, so either throw an exception or return an error value.

All digits are the same

How to Handle:

Arrange the digits in ascending order which will result in the number itself.