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, odd_heap and even_heap, 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 even_heap.

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

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 even_heap and append it to result.

   2. If the digit is odd, pop the digit from odd_heap 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: