Largest Number After Digit Swaps by Parity

Largest Number After Digit Swaps by Parity - Problem

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 performing any number of such swaps.

Note: Digits with the same parity can be rearranged in any order to maximize the number.

Input & Output

Example 1 — Basic Case

$ Input: num = 1234

› Output: 3214

💡 Note: Odd digits [1,3] can be rearranged to [3,1], even digits [2,4] to [4,2]. Result: 3214

Example 2 — Same Parity Only

$ Input: num = 65875

› Output: 87655

💡 Note: Odd digits [5,7,5] sorted descending: [7,5,5]. Even digits [6,8] sorted: [8,6]. Result: 87655

Example 3 — Already Optimal

$ Input: num = 247

› Output: 427

💡 Note: Even digits [2,4] become [4,2], odd digit [7] stays. Result: 427

Constraints

1 ≤ num ≤ 10⁹
num consists of digits only

Visualization

Tap to expand

Understanding the Visualization

Input

Number 1234 with odd digits [1,3] and even digits [2,4]

Process

Sort odds [3,1] and evens [4,2] in descending order

Output

Reconstruct to get maximum value: 3214

Key Takeaway

🎯 Key Insight: Digits of the same parity can be freely rearranged - sort them descending for maximum value

Asked in

G Google 15 a Amazon 12

The key insight is that digits with the same parity can be rearranged freely. The optimal approach separates digits by parity, sorts each group in descending order, then reconstructs the number. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Sort by Parity - Optimal	O(n log n)	O(n)	Separate digits by parity, sort each group descending, then reconstruct
Brute Force - Try All Swaps	O(n! × n)	O(n)	Generate all possible numbers by trying every valid swap combination

Sort by Parity - Optimal — Algorithm Steps

Convert number to digit array
Separate digits into odd and even lists
Sort both lists in descending order
Reconstruct number by placing sorted digits back

Visualization

Tap to expand

Step-by-Step Walkthrough

Separate

Split digits into odd [1,3] and even [2,4] groups

Sort

Sort each group descending: [3,1] and [4,2]

Reconstruct

Place sorted digits back: 3214

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare_desc(const void *a, const void *b) {
    return (*(char*)b - *(char*)a);
}

int solution(int num) {
    char digits[20];
    sprintf(digits, "%d", num);
    int n = strlen(digits);
    
    char odds[20], evens[20];
    int oddCount = 0, evenCount = 0;
    
    // Separate digits by parity
    for (int i = 0; i < n; i++) {
        if ((digits[i] - '0') % 2 == 0) {
            evens[evenCount++] = digits[i];
        } else {
            odds[oddCount++] = digits[i];
        }
    }
    
    // Sort both in descending order
    qsort(odds, oddCount, sizeof(char), compare_desc);
    qsort(evens, evenCount, sizeof(char), compare_desc);
    
    // Reconstruct number
    char result[20];
    int oddIdx = 0, evenIdx = 0;
    
    for (int i = 0; i < n; i++) {
        if ((digits[i] - '0') % 2 == 0) {
            result[i] = evens[evenIdx++];
        } else {
            result[i] = odds[oddIdx++];
        }
    }
    result[n] = '\0';
    
    return atoi(result);
}

int main() {
    int num;
    scanf("%d", &num);
    int result = solution(num);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting the digits takes O(n log n) where n is number of digits

⚡ Linearithmic

Space Complexity

O(n)

Store digit arrays and separate odd/even lists

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort by Parity - Optimal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler