algoadvance

Given a positive integer num, you are allowed to swap any two digits with the same parity (any number of times). Your task is to return the largest possible number that can be obtained through these swaps.

Clarifying Questions

  1. Does the input number have any specific restrictions?
    • No, the input is any positive integer.
  2. How do we define parity for the digits?
    • Parity is defined as even or odd. Digits that are even can only be swapped with other even digits, and odd digits can only be swapped with other odd digits.
  3. Are the digits constrained only to base-10?
    • Yes, since it’s a decimal number, the digits are from 0 to 9.

Strategy

  1. Identify Digits by Parity: Separate the digits of the given number into two groups: even and odd.
  2. Sort Each Group Descending: For each group, sort the digits in descending order.
  3. Reconstruct the Number: Iterate through the original number and replace each digit with the next largest from the respective sorted group.
  4. Combine and Return: Combine the digits to form the new largest number.

Code

Here is the Python implementation of the strategy:

def largestNumberByParitySwaps(num: int) -> int:
    # Convert number to list of digits
    digits = list(map(int, str(num)))
    
    # Separate digits by parity
    even_digits = sorted([d for d in digits if d % 2 == 0], reverse=True)
    odd_digits = sorted([d for d in digits if d % 2 != 0], reverse=True)
    
    # Variables to track the positions in sorted parity lists
    even_idx, odd_idx = 0, 0
    
    # Resultant list of digits
    result_digits = []
    
    for d in digits:
        if d % 2 == 0:
            # The next largest even digit
            result_digits.append(even_digits[even_idx])
            even_idx += 1
        else:
            # The next largest odd digit
            result_digits.append(odd_digits[odd_idx])
            odd_idx += 1
    
    # Convert the list of digits back to integer
    return int(''.join(map(str, result_digits)))

# Example usage:
print(largestNumberByParitySwaps(65875)) # Output should be the largest number obtained

Time Complexity

  1. Separating Digits by Parity: O(n), where n is the number of digits in num.
  2. Sorting the Even and Odd Lists: O(n log n), as each list can contain at most all the digits.
  3. Reconstructing the Largest Number: O(n), to iterate through the original digits and reconstruct the result.

Overall, the time complexity is dominated by the sorting step, thus O(n log n).

Try our interview co-pilot at AlgoAdvance.com