Jobs

Interviews

Discussions

Largest Number After Digit Swaps by Parity

Easy

Asked by:

16 views

Topics:

ArraysGreedy AlgorithmsStrings

You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).

Return the largest possible value of num after any number of swaps.

Example 1:

Input: num = 1234
Output: 3412
Explanation: Swap the digit 3 with the digit 1, this results in the number 3214.
Swap the digit 2 with the digit 4, this results in the number 3412.
Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number.
Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.

Example 2:

Input: num = 65875
Output: 87655
Explanation: Swap the digit 8 with the digit 6, this results in the number 85675.
Swap the first digit 5 with the digit 7, this results in the number 87655.
Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.

Constraints:

1 <= num <= 10⁹

Try coding it in LeetCode

Largest Number After Digit Swaps by Parity

Easy

Asked by:

16 views

Topics:

ArraysGreedy AlgorithmsStrings

You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).

Return the largest possible value of num after any number of swaps.

Example 1:

Input: num = 1234
Output: 3412
Explanation: Swap the digit 3 with the digit 1, this results in the number 3214.
Swap the digit 2 with the digit 4, this results in the number 3412.
Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number.
Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.

Example 2:

Input: num = 65875
Output: 87655
Explanation: Swap the digit 8 with the digit 6, this results in the number 85675.
Swap the first digit 5 with the digit 7, this results in the number 87655.
Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.

Constraints:

1 <= 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:

What is the maximum possible value of the input integer `num`? This will help me understand potential data type limitations.
Can the input integer `num` ever be zero or negative?
If the input is a single digit, should I just return it as a string?
Are leading zeros allowed in the returned string? If not, how should I handle a case where all digits become zero after some hypothetical operation (although it is impossible in this question)?
Is the goal to return the *largest* possible integer representable as a string, even if there are multiple possible swap sequences that lead to the same maximal number?

Brute Force Solution

Approach

The brute force approach to finding the largest number after digit swaps by parity means trying every possible combination of swaps. We generate each possible new number by swapping digits of the same parity and see which one is the largest.

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

Consider the original number as a sequence of digits.
Look at every pair of digits in the number.
Check if both digits in the pair are either both even or both odd.
If they are both even or both odd, swap them to create a new number.
Repeat the previous steps for every possible pair of even/odd digits, creating a list of all possible swapped numbers.
Compare all the new numbers you created, along with the original number.
Select the largest number from this comparison. That's your answer.

Code Implementation

def largest_number_after_digit_swaps_by_parity_brute_force(number):
    number_string = str(number)
    digits_length = len(number_string)
    possible_numbers = [number_string]

    # Generate all possible swapped numbers.
    for first_digit_index in range(digits_length):
        for second_digit_index in range(first_digit_index + 1, digits_length):
            first_digit = int(number_string[first_digit_index])
            second_digit = int(number_string[second_digit_index])

            # Only swap if both digits are even or both are odd.
            if (first_digit % 2) == (second_digit % 2):
                new_number_string = list(number_string)
                new_number_string[first_digit_index], new_number_string[second_digit_index] = \
                    new_number_string[second_digit_index], new_number_string[first_digit_index]
                possible_numbers.append("".join(new_number_string))

    # Convert all string representations to integers.
    possible_numbers_int = [int(number) for number in possible_numbers]

    # Find the largest number among all possibilities.
    largest_number = number

    # Ensure to include the original number too
    for possible_number in possible_numbers_int:
        if possible_number > largest_number:
            largest_number = possible_number

    return largest_number

Big(O) Analysis

Time Complexity

O(n²) – Let n be the number of digits in the input number. The brute force approach involves checking every pair of digits to see if they have the same parity. We iterate through all possible pairs of digits, which requires nested loops. The outer loop iterates n times, and the inner loop also iterates up to n times in the worst case. Therefore, the total number of comparisons approximates n * n/2, leading to a time complexity of O(n²).

Space Complexity

O(N!) – The brute force approach generates all possible numbers by swapping digits of the same parity. In the worst-case scenario, every pair of digits might be swappable, leading to the creation of a large number of new numbers. If N is the number of digits in the input number, the number of possible swaps could approach N! (N factorial) as we explore different combinations. Storing all these potentially swapped numbers contributes to the auxiliary space, leading to O(N!) space complexity. We need to store these swapped numbers, and in the worst case, this number can grow factorially.

Optimal Solution

Approach

To get the largest possible number, we want to put the biggest digits in the most significant places. We'll separate the even and odd digits, then strategically place them back in the original number.

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

First, separate all the even digits and all the odd digits from the original number into two separate collections.
Sort each of these collections in descending order (biggest to smallest).
Now, go through the original number, one digit at a time. If the original digit was even, replace it with the next largest even digit from your sorted even digit collection.
If the original digit was odd, replace it with the next largest odd digit from your sorted odd digit collection.
Finally, put all the digits back together in the same order as the original number. This will be the largest possible number you can make by swapping digits of the same parity.

Code Implementation

def largest_number_after_digit_swaps_by_parity(number):
    number_string = str(number)
    even_digits = []
    odd_digits = []

    for digit in number_string:
        digit_value = int(digit)
        if digit_value % 2 == 0:
            even_digits.append(digit_value)
        else:
            odd_digits.append(digit_value)

    even_digits.sort(reverse=True)
    odd_digits.sort(reverse=True)

    even_index = 0
    odd_index = 0
    result = ''

    # Building the result string by picking the largest digits
    for digit in number_string:
        digit_value = int(digit)

        if digit_value % 2 == 0:
            # Preserve parity by using digits of the same parity only.
            result += str(even_digits[even_index])
            even_index += 1
        else:
            # Preserve parity by using digits of the same parity only.
            result += str(odd_digits[odd_index])
            odd_index += 1

    return int(result)

Big(O) Analysis

Time Complexity

O(n log n) – Separating even and odd digits from the input number, which has n digits, takes O(n) time. Sorting the even and odd digit collections each take O(k log k) time, where k is the number of even/odd digits. Since k <= n, this is bounded by O(n log n). Iterating through the original number and replacing digits based on parity takes O(n) time. Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The algorithm creates two collections (lists or arrays) to store the even and odd digits separately. In the worst-case scenario, all digits of the input number are either even or odd, resulting in one of these collections holding N digits, where N is the number of digits in the input number. Therefore, the auxiliary space used is proportional to the input size N. The sorting of these collections uses an in-place sort, or a constant number of additional variables.

Edge Cases

Case	How to Handle
Input num is 0	The algorithm should correctly handle 0 and return '0'.
Input num is a single-digit number	The algorithm should return the input number as a string without any changes.
Input num has all even digits	The algorithm should sort the even digits in descending order and return the result.
Input num has all odd digits	The algorithm should sort the odd digits in descending order and return the result.
Input num has digits in descending order already	The algorithm should return the input number as a string since no swaps are needed.
Large input number (e.g., a number with 100 digits)	The algorithm's time complexity should be considered; sorting digits is generally efficient, but ensure no excessive memory is used by converting to string for processing.
Leading zeros after swaps	The algorithm should handle leading zeros correctly after potentially swapping digits to achieve the largest number (leading zeros are acceptable in the result string).
Integer overflow when converting back to integer	The solution should work with the number as a string to avoid integer overflow during intermediate calculations or final representation.

Input num is 0

How to Handle:

The algorithm should correctly handle 0 and return '0'.

Input num is a single-digit number

How to Handle:

The algorithm should return the input number as a string without any changes.

Input num has all even digits

How to Handle:

The algorithm should sort the even digits in descending order and return the result.

Input num has all odd digits

How to Handle:

The algorithm should sort the odd digits in descending order and return the result.

Input num has digits in descending order already

How to Handle:

The algorithm should return the input number as a string since no swaps are needed.

Large input number (e.g., a number with 100 digits)

How to Handle:

The algorithm's time complexity should be considered; sorting digits is generally efficient, but ensure no excessive memory is used by converting to string for processing.

Leading zeros after swaps

How to Handle:

The algorithm should handle leading zeros correctly after potentially swapping digits to achieve the largest number (leading zeros are acceptable in the result string).

Integer overflow when converting back to integer

How to Handle:

The solution should work with the number as a string to avoid integer overflow during intermediate calculations or final representation.

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:

What is the maximum possible value of the input integer `num`? This will help me understand potential data type limitations.
Can the input integer `num` ever be zero or negative?
If the input is a single digit, should I just return it as a string?
Are leading zeros allowed in the returned string? If not, how should I handle a case where all digits become zero after some hypothetical operation (although it is impossible in this question)?
Is the goal to return the *largest* possible integer representable as a string, even if there are multiple possible swap sequences that lead to the same maximal number?

Brute Force Solution

Approach

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

Consider the original number as a sequence of digits.
Look at every pair of digits in the number.
Check if both digits in the pair are either both even or both odd.
If they are both even or both odd, swap them to create a new number.
Repeat the previous steps for every possible pair of even/odd digits, creating a list of all possible swapped numbers.
Compare all the new numbers you created, along with the original number.
Select the largest number from this comparison. That's your answer.

Code Implementation

def largest_number_after_digit_swaps_by_parity_brute_force(number):
    number_string = str(number)
    digits_length = len(number_string)
    possible_numbers = [number_string]

    # Generate all possible swapped numbers.
    for first_digit_index in range(digits_length):
        for second_digit_index in range(first_digit_index + 1, digits_length):
            first_digit = int(number_string[first_digit_index])
            second_digit = int(number_string[second_digit_index])

            # Only swap if both digits are even or both are odd.
            if (first_digit % 2) == (second_digit % 2):
                new_number_string = list(number_string)
                new_number_string[first_digit_index], new_number_string[second_digit_index] = \
                    new_number_string[second_digit_index], new_number_string[first_digit_index]
                possible_numbers.append("".join(new_number_string))

    # Convert all string representations to integers.
    possible_numbers_int = [int(number) for number in possible_numbers]

    # Find the largest number among all possibilities.
    largest_number = number

    # Ensure to include the original number too
    for possible_number in possible_numbers_int:
        if possible_number > largest_number:
            largest_number = possible_number

    return largest_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, separate all the even digits and all the odd digits from the original number into two separate collections.
Sort each of these collections in descending order (biggest to smallest).
Now, go through the original number, one digit at a time. If the original digit was even, replace it with the next largest even digit from your sorted even digit collection.
If the original digit was odd, replace it with the next largest odd digit from your sorted odd digit collection.
Finally, put all the digits back together in the same order as the original number. This will be the largest possible number you can make by swapping digits of the same parity.

Code Implementation

def largest_number_after_digit_swaps_by_parity(number):
    number_string = str(number)
    even_digits = []
    odd_digits = []

    for digit in number_string:
        digit_value = int(digit)
        if digit_value % 2 == 0:
            even_digits.append(digit_value)
        else:
            odd_digits.append(digit_value)

    even_digits.sort(reverse=True)
    odd_digits.sort(reverse=True)

    even_index = 0
    odd_index = 0
    result = ''

    # Building the result string by picking the largest digits
    for digit in number_string:
        digit_value = int(digit)

        if digit_value % 2 == 0:
            # Preserve parity by using digits of the same parity only.
            result += str(even_digits[even_index])
            even_index += 1
        else:
            # Preserve parity by using digits of the same parity only.
            result += str(odd_digits[odd_index])
            odd_index += 1

    return int(result)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input num is 0	The algorithm should correctly handle 0 and return '0'.
Input num is a single-digit number	The algorithm should return the input number as a string without any changes.
Input num has all even digits	The algorithm should sort the even digits in descending order and return the result.
Input num has all odd digits	The algorithm should sort the odd digits in descending order and return the result.
Input num has digits in descending order already	The algorithm should return the input number as a string since no swaps are needed.
Large input number (e.g., a number with 100 digits)	The algorithm's time complexity should be considered; sorting digits is generally efficient, but ensure no excessive memory is used by converting to string for processing.
Leading zeros after swaps	The algorithm should handle leading zeros correctly after potentially swapping digits to achieve the largest number (leading zeros are acceptable in the result string).
Integer overflow when converting back to integer	The solution should work with the number as a string to avoid integer overflow during intermediate calculations or final representation.

Input num is 0

How to Handle:

The algorithm should correctly handle 0 and return '0'.

Input num is a single-digit number

How to Handle:

The algorithm should return the input number as a string without any changes.

Input num has all even digits

How to Handle:

The algorithm should sort the even digits in descending order and return the result.

Input num has all odd digits

How to Handle:

The algorithm should sort the odd digits in descending order and return the result.

Input num has digits in descending order already

How to Handle:

The algorithm should return the input number as a string since no swaps are needed.

Large input number (e.g., a number with 100 digits)

How to Handle:

The algorithm's time complexity should be considered; sorting digits is generally efficient, but ensure no excessive memory is used by converting to string for processing.

Leading zeros after swaps

How to Handle:

The algorithm should handle leading zeros correctly after potentially swapping digits to achieve the largest number (leading zeros are acceptable in the result string).

Integer overflow when converting back to integer

How to Handle:

The solution should work with the number as a string to avoid integer overflow during intermediate calculations or final representation.