{x}
blog image

Largest Number After Digit Swaps by Parity

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 <= 109

Solution Explanation for Largest Number After Digit Swaps by Parity

This problem asks us to find the largest possible integer we can create by swapping digits of the same parity (even or odd) within a given integer.

Approach

The most efficient approach involves the following steps:

  1. Digit Extraction and Parity Check: Convert the input integer into a string or array of digits. Determine the parity (even or odd) of each digit.

  2. Separate Even and Odd Digits: Separate the digits into two lists: one for even digits and one for odd digits.

  3. Sort the Digits: Sort the even and odd digit lists in descending order. This is crucial for creating the largest possible number.

  4. Reassemble the Number: Iterate through the original digit order. For each digit, replace it with the largest available digit from its corresponding (even or odd) sorted list. Keep track of which digits in the sorted lists have already been used.

  5. Construct the Result: Finally, convert the modified list of digits back into an integer.

Code Implementation (Python)

def largestInteger(num: int) -> int:
    digits = list(str(num))  #Convert to list of strings
    n = len(digits)
    odds = []
    evens = []
    for i in range(n):
        digit = int(digits[i])
        if digit % 2 == 0:
            evens.append(digit)
        else:
            odds.append(digit)
    
    odds.sort(reverse=True) #sort descending
    evens.sort(reverse=True)
    
    odd_idx = 0
    even_idx = 0
    result = []
    for i in range(n):
        digit = int(digits[i])
        if digit % 2 == 0:
            result.append(str(evens[even_idx]))
            even_idx +=1
        else:
            result.append(str(odds[odd_idx]))
            odd_idx +=1
 
    return int("".join(result))

Time and Space Complexity Analysis

  • Time Complexity: O(N log N), where N is the number of digits in the input integer. The dominant factor is the sorting of the even and odd digit lists (using a typical comparison-based sorting algorithm like merge sort or quicksort).

  • Space Complexity: O(N). This is because we create lists to store even and odd digits, which can have at most N elements each. The result list also has N elements.

Other Language Implementations (Conceptual)

The same core approach can be implemented in other languages, with minor syntactical differences. The key steps remain the same:

  • Digit extraction and parity checking: This might involve converting to strings or arrays in most languages.
  • Sorting: Using built-in sorting functions (sort() in Python, Arrays.sort() in Java, std::sort() in C++ etc.)
  • Reassembling: Iterating and replacing digits based on the sorted lists and parity.
  • Result conversion: Converting the modified digit list (array or string) back to an integer.

The time and space complexity would remain the same across different language implementations.