Problem Statement:

Given a non-negative integer num, rearrange the digits of num such that the resulting number is also non-negative and maximal.

Return the largest such number possible.

Examples:

Input: num = 2736 Output: 7236 Explanation: Swap the number 2 and the number 7.

Input: num = 9973 Output: 9973 Explanation: No swaps needed.

Input: num = 1191 Output: 9911 Explanation: Swap the number 1 and the number 9.

Solution:

This problem can be simplified by categorizing the digits in the number as even or odd. Once the digits have been divided into even and odd groups, the largest even digit will be swapped with the leftmost (highest value) even digit. Similarly, the largest odd digit will be swapped with the leftmost (highest value) odd digit. This is because moving the largest even or odd digit to the leftmost position will result in the maximum number. If there are no even digits remaining, swap odd digits or vice versa. If there are no even or odd digits left, it means the maximum number has been found and the function can terminate.

To implement this in code, first, we need to convert the integer to a string, so we can access each digit. Next, we need to separate the odd and even digits into separate arrays. In the next step, we will sort each array in descending order. Finally, we will swap the largest even digit with the leftmost even digit and the largest odd digit with the leftmost odd digit. If there are no even digits or odd digits left, we can terminate the function and return the final number.

Here is the implementation of the solution in Python:

def largestNumber(num: int) -> int: s = str(num) odd_digits = [] even_digits = []

for char in s:
    if int(char) % 2 == 0:
        even_digits.append(int(char))
    else:
        odd_digits.append(int(char))

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

result = []
while odd_digits or even_digits:
    if odd_digits and even_digits:
        if even_digits[0] > odd_digits[0]:
            result.append(str(even_digits[0]))
            even_digits.pop(0)
        else:
            result.append(str(odd_digits[0]))
            odd_digits.pop(0)
    elif even_digits:
        result.append(str(even_digits[0]))
        even_digits.pop(0)
    elif odd_digits:
        result.append(str(odd_digits[0]))
        odd_digits.pop(0)

return int("".join(result))

Test the function with some examples

print(largestNumber(2736)) # Expected Output: 7236 print(largestNumber(9973)) # Expected Output: 9973 print(largestNumber(1191)) # Expected Output: 9911

The time complexity of this solution is O(NlogN), where N is the number of digits in the input number. This is because sorting the two arrays has a time complexity of O(NlogN), and the while loop runs at most twice, which is O(N) in the worst case.

1