Here is one of the easy ones from the Leetcode Contest challenge a couple of weeks ago.

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.

The Problem

We are only allowed to swap either odd or even digits in this problem and should continue doing so until we get the largest possible number.

In the following example, 1234, we can swap 3 and 1 since they are in odd positions. If a digit X was greater than 3 and an odd number, it would be moved into the most significant position occupied by 1.

Here are some other examples. In the following diagram, 4 and 2 can be swapped to produce 427, the largest possible number after swapping.

In the following diagram, digit swaps produce 3142

Solution

Approach 1

My original approach is to convert the number into an array and generate 2 arrays. One array contains all the even numbers, while the other has all the odd numbers.

The original positions of all the odd numbers will be preserved in a separate set.

It is now possible to sort each of these separate arrays individually and then merge them using the Set of odd number positions.

In the first example, the answer 3412 is the result of merging two separate sorted arrays [3,1] and [4,2] while ensuring that the odd numbers are only placed at positions 0 and 2

In the second example, the sorted arrays [7] and [4,2] are merged together while ensuring the odd numbers only occupy position 2, and hence the result [4,2,7]

Approach 2

My second approach involved converting the number into a doubly-linked list and then running a sort algorithm that accounted for odd and even numbers in parallel. The complexity of this solution caused me to write code based on approach 1

Code

Converting the number into an array

This is simple code that converts a number into an array

def convertNumberToArr(num):
    
    arr = []

    while (num  != 0):
        arr.append( num % 10 )
        num = num // 10

    arr.reverse()
    return arr

Splitting the array into Odd and Even arrays

The following method simply splits the array into two arrays containing sorted odd and even numbers

def getOddEvenNumbers(arr):

    oddPositions = set()
    even, odd = [] , []
  
    for i,value in enumerate(arr):
        
        if (value % 2 == 1): 
            odd.append(value)
            oddPositions.add(i)
        else:
            even.append(value)

    odd.sort(reverse=True)
    even.sort(reverse=True)

    return (odd,even,oddPositions)

Generating the Largest Integer

Finally putting the two methods above together, the following code merges the two sorted arrays and then converts the array back into a number

def largestInteger(self, num):

    numbers = convertNumberToArr(num)

    odd,even,oddPositions = getOddEvenNumbers(numbers)
    
    retValue = []

    oddI = 0
    evenI = 0

    for i,value in enumerate(numbers):
        
        # check if odd or even and also account 
        # for which parity is the starting digit
        if i in oddPositions and ((i == 0 and i in oddPositions) or i != 0):
            retValue.append(odd[oddI])
            oddI += 1
        else:
            retValue.append(even[evenI])
            evenI += 1

    retNum = 0

    for val in retValue:
        retNum = (retNum * 10) + val

    return retNum

Jason Coelho

Largest Number After Digit Swaps by Parity