Largest Number After Digit Swaps by Parity

Easy

#2032Time: O(D log D), where D is the number of digits in `num`. The dominant operation is sorting the lists of digits. Converting the number to/from a string and iterating through it takes O(D) time.Space: O(D), where D is the number of digits in `num`. This space is used to store the string representation of the number, the two lists of digits, and the `StringBuilder` for the result.1 company

Algorithms

Sorting

Data structures

Heap (Priority Queue)

Companies

ZScaler

Prompt

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 <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

The core idea is that we can freely swap any two digits of the same parity. This means we can arrange all the odd digits in any order among their original positions, and similarly for the even digits. To get the largest number, we should place the largest digits at the most significant positions (leftmost). This can be achieved by sorting the odd and even digits separately in descending order and then reconstructing the number by placing the sorted digits back into their original parity-based positions.

Algorithm

Convert the input number num into a string s.
Create two separate lists: oddDigits and evenDigits.
Iterate through the characters of s. If a digit is odd, add it to the oddDigits list. If it's even, add it to the evenDigits list.
Sort the oddDigits list in descending order.
Sort the evenDigits list in descending order.
Initialize two pointers, oddIndex = 0 and evenIndex = 0.
Create a StringBuilder to construct the result.
Iterate through the characters of the original string s again. For each character:
- If the original digit was odd, append the digit from oddDigits at oddIndex to the result and increment oddIndex.
- If the original digit was even, append the digit from evenDigits at evenIndex to the result and increment evenIndex.
Convert the StringBuilder back to an integer and return it.

Walkthrough

This approach involves separating the digits of the number into two groups based on their parity (odd or even). Each group of digits can be rearranged arbitrarily among themselves. To maximize the final number, we should use the largest available digits in the most significant positions. Therefore, we sort both the odd and even digits in descending order. Then, we reconstruct the number by iterating through the original number's digit positions. For each position, we determine its original parity and place the next largest digit from the corresponding sorted list.

For example, with num = 1234:

Original digits: 1, 2, 3, 4. Parity pattern: Odd, Even, Odd, Even.
Odd digits: 1, 3. Even digits: 2, 4.
Sorted odd digits (descending): 3, 1. Sorted even digits (descending): 4, 2.
Reconstruct:
- 1st position (Odd): Use largest odd digit 3.
- 2nd position (Even): Use largest even digit 4.
- 3rd position (Odd): Use next largest odd digit 1.
- 4th position (Even): Use next largest even digit 2.
Result: 3412.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public int largestInteger(int num) {7        String s = String.valueOf(num);8        List<Character> oddDigits = new ArrayList<>();9        List<Character> evenDigits = new ArrayList<>();10 11        for (char c : s.toCharArray()) {12            int digit = c - '0';13            if (digit % 2 == 0) {14                evenDigits.add(c);15            } else {16                oddDigits.add(c);17            }18        }19 20        // Sort in descending order21        Collections.sort(oddDigits, Collections.reverseOrder());22        Collections.sort(evenDigits, Collections.reverseOrder());23 24        StringBuilder result = new StringBuilder();25        int oddIndex = 0;26        int evenIndex = 0;27 28        for (char c : s.toCharArray()) {29            int digit = c - '0';30            if (digit % 2 == 0) {31                result.append(evenDigits.get(evenIndex++));32            } else {33                result.append(oddDigits.get(oddIndex++));34            }35        }36 37        return Integer.parseInt(result.toString());38    }39}

Complexity

Time

O(D log D), where D is the number of digits in `num`. The dominant operation is sorting the lists of digits. Converting the number to/from a string and iterating through it takes O(D) time.

Space

O(D), where D is the number of digits in `num`. This space is used to store the string representation of the number, the two lists of digits, and the `StringBuilder` for the result.

Trade-offs

Pros

Relatively simple to understand and implement.
Correctly solves the problem by identifying the core property of swappable groups.

Cons

Not the most optimal solution in terms of time complexity, as sorting can be done more efficiently for a small, fixed range of values (digits 0-9).

This approach improves upon the previous one by using a more efficient sorting algorithm suitable for the problem's constraints. Since the values to be sorted are single digits (0-9), we can use Counting Sort, which has a linear time complexity. We count the occurrences of each odd and even digit and then reconstruct the number by picking the largest available digits of the correct parity for each position.

Algorithm

Convert num to a string s.
Create two frequency arrays, oddCounts and evenCounts, of size 10, initialized to zeros.
Iterate through each character c in s:
- Let digit be the integer value of c.
- If digit is even, increment evenCounts[digit].
- Otherwise, increment oddCounts[digit].
Initialize a StringBuilder result.
Iterate through each character c in s again:
- Let digit be the integer value of c.
- If digit is even (i.e., the original position held an even number):
  - Find the largest d from 8 down to 0 (by 2s) such that evenCounts[d] > 0.
  - Append d to result and decrement evenCounts[d].
  - Break the inner search loop.
- If digit is odd:
  - Find the largest d from 9 down to 1 (by 2s) such that oddCounts[d] > 0.
  - Append d to result and decrement oddCounts[d].
  - Break the inner search loop.
Convert result to an integer and return it.

Walkthrough

Instead of a general-purpose comparison sort, we can use a more specialized and faster algorithm given that we are only sorting digits. Counting sort is ideal here. We can use two frequency arrays, one for odd digits and one for even digits, to count the occurrences of each.

After counting, we reconstruct the number. We iterate through the original number's positions one by one. If a position originally held an even number, we find the largest even digit we have in our frequency map, append it to our result, and decrement its count. We do the same for positions that originally held an odd number. This ensures that the largest digits are placed in the most significant positions possible while respecting the parity constraints.

1class Solution {2    public int largestInteger(int num) {3        String s = String.valueOf(num);4        int[] oddCounts = new int[10];5        int[] evenCounts = new int[10];6 7        for (char c : s.toCharArray()) {8            int digit = c - '0';9            if (digit % 2 == 0) {10                evenCounts[digit]++;11            } else {12                oddCounts[digit]++;13            }14        }15 16        StringBuilder result = new StringBuilder();17        for (char c : s.toCharArray()) {18            int digit = c - '0';19            if (digit % 2 == 0) { // Position requires an even digit20                // Find the largest available even digit21                for (int d = 8; d >= 0; d -= 2) {22                    if (evenCounts[d] > 0) {23                        result.append(d);24                        evenCounts[d]--;25                        break;26                    }27                }28            } else { // Position requires an odd digit29                // Find the largest available odd digit30                for (int d = 9; d >= 1; d -= 2) {31                    if (oddCounts[d] > 0) {32                        result.append(d);33                        oddCounts[d]--;34                        break;35                    }36                }37            }38        }39        return Integer.parseInt(result.toString());40    }41}

Complexity

Time

O(D), where D is the number of digits in `num`. Converting to a string, populating the count arrays, and reconstructing the number each take O(D) time. The inner loops for finding the next digit run a constant number of times, so the total time complexity is linear.

Space

O(D), where D is the number of digits in `num`. We use O(1) space for the count arrays (constant size). The space is dominated by storing the string representation of the number (`O(D)`) and the `StringBuilder` for the result (`O(D)`).

Trade-offs

Pros

Most efficient approach with linear time complexity.
Avoids the overhead of comparison-based sorting.

Cons

Slightly more complex to implement than the direct sorting approach due to managing frequency arrays.

Solutions

Solution

1class Solution {2public3  int largestInteger(int num) {4    int[] cnt = new int[10];5    int x = num;6    while (x != 0) {7      cnt[x % 10]++;8      x /= 10;9    }10    x = num;11    int ans = 0;12    int t = 1;13    while (x != 0) {14      int v = x % 10;15      x /= 10;16      for (int y = 0; y < 10; ++y) {17        if (((v ^ y) & 1) == 0 && cnt[y] > 0) {18          cnt[y]--;19          ans += y * t;20          t *= 10;21          break;22        }23      }24    }25    return ans;26  }27}

1class Solution {2public:3  int largestInteger(int num) {4    vector<int> cnt(10);5    int x = num;6    while (x) {7      cnt[x % 10]++;8      x /= 10;9    }10    x = num;11    int ans = 0;12    long t = 1;13    while (x) {14      int v = x % 10;15      x /= 10;16      for (int y = 0; y < 10; ++y) {17        if (((v ^ y) & 1) == 0 && cnt[y] > 0) {18          cnt[y]--;19          ans += y * t;20          t *= 10;21          break;22        }23      }24    }25    return ans;26  }27};

1class Solution:2    def largestInteger(self, num: int) -> int: cnt = Counter() x = num while x: x, v = divmod(x, 10) cnt[v] += 1 x = num ans = 0 t = 1 while x: x, v = divmod(x, 10) for y in range(10): if ((v ^ y) & 1) == 0 and cnt[y]: ans += y * t t *= 10 cnt[y] -= 1 break return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem