We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Largest Number After Digit Swaps by Parity

Difficulty: Easy

Problem Description

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.

Key Insights

  • Digits can be classified into two categories: even and odd.
  • We can freely swap digits within each category to form the largest number possible.
  • The largest number can be achieved by sorting even digits and odd digits independently in descending order.
  • After sorting, we reconstruct the number by placing the digits back in their original positions according to their parity.

Space and Time Complexity

Time Complexity: O(n log n), where n is the number of digits in the number (due to sorting). Space Complexity: O(n), for storing the digits and the sorted digits.

Solution

To solve this problem, we will follow these steps:

  1. Convert the number into a list of its digits.
  2. Separate the digits into two lists based on their parity: one for even digits and another for odd digits.
  3. Sort both lists in descending order.
  4. Reconstruct the number by iterating through the original list of digits and replacing them with the next largest digit from the corresponding sorted list based on their parity.

This approach ensures that we get the largest possible number after the allowed swaps.

Code Solutions

def largest_number_after_swaps(num):
    digits = [int(d) for d in str(num)]
    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)
    
    even_index, odd_index = 0, 0
    result = []
    
    for d in digits:
        if d % 2 == 0:
            result.append(even_digits[even_index])
            even_index += 1
        else:
            result.append(odd_digits[odd_index])
            odd_index += 1
            
    return int(''.join(map(str, result)))

# Example usage:
print(largest_number_after_swaps(1234))  # Output: 3412
print(largest_number_after_swaps(65875)) # Output: 87655
← Back to All Questions