Solution: Largest Number After Digit Swaps by Parity

Statement

You are given a positive integer num. You can swap any two digits of num as long as they share the same parity (both are odd or both are even).

Your task is to return the largest possible value of num after performing any number of such swaps.

Constraints:

• $1 \leq$ num $\leq 10^9$

Solution

The algorithm rearranges the digits of a given integer num to form the largest possible number by allowing swaps only between digits that share the same parity (either odd or even). To achieve this, it uses two max-heaps—one for odd digits and one for even digits—which enable efficient storage and retrieval of the largest available digits in each parity group. As it iterates through the digits, the algorithm replaces each digit with the largest possible digit of the same parity from its respective heap. There’s no need to compare the current digit with the digit from the heap because the largest digit of each parity is always at the top of its heap, it can be popped directly and appended to the result. This ensures the final number is maximized while following to the parity constraint, ultimately producing the largest possible value that can be constructed from num.

The steps of the algorithm are as follows:

1. Convert the integer num into a list digits that contains each individual digit.

2. Create two empty max-heaps, oddHeap and evenHeap, to store the odd and even digits, respectively.

3. Iterate through each digit in the digits list:

   1. If the digit is even, push it onto evenHeap.

   2. If the digit is odd, push it onto oddHeap.

4. Initialize an empty list result to construct the final number.

5. Iterate through each digit in the digits list:

   1. If the digit is even, pop the digit from evenHeap and append it to result.

   2. If the digit is odd, pop the digit from oddHeap and append it to result.

6. Join the elements of result into a single string, then convert it back to an integer and return result.

Let’s look at the following illustration to get a better understanding of the solution: