2231. Largest Number After Digit Swaps by Parity LeetCode Solution

In this guide, you will get 2231. Largest Number After Digit Swaps by Parity LeetCode Solution with the best time and space complexity. The solution to Largest Number After Digit Swaps by Parity problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Largest Number After Digit Swaps by Parity solution in C++
Largest Number After Digit Swaps by Parity solution in Java
Largest Number After Digit Swaps by Parity solution in Python
Additional Resources

2231. Largest Number After Digit Swaps by Parity LeetCode Solution image

Problem Statement of 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

Complexity Analysis

Time Complexity: O(\log\texttt{num})
Space Complexity: O(\log\texttt{num})

2231. Largest Number After Digit Swaps by Parity LeetCode Solution in C++

class Solution {
 public:
  int largestInteger(int num) {
    const string s = to_string(num);
    int ans = 0;
    // maxHeap[0] := the odd digits
    // maxHeap[1] := the even digits
    vector<priority_queue<int>> maxHeap(2);

    for (const char c : s) {
      const int digit = c - '0';
      maxHeap[digit % 2].push(digit);
    }

    for (const char c : s) {
      const int i = c - '0' & 1;
      ans *= 10;
      ans += maxHeap[i].top(), maxHeap[i].pop();
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2231. Largest Number After Digit Swaps by Parity LeetCode Solution in Java

class Solution {
  public int largestInteger(int num) {
    final String s = String.valueOf(num);
    int ans = 0;
    // maxHeap[0] := the odd digits
    // maxHeap[1] := the even digits
    Queue<Integer>[] maxHeap = new Queue[2];

    for (int i = 0; i < 2; ++i)
      maxHeap[i] = new PriorityQueue<>(Comparator.reverseOrder());

    for (final char c : s.toCharArray()) {
      final int digit = c - '0';
      maxHeap[digit % 2].offer(digit);
    }

    for (final char c : s.toCharArray()) {
      final int i = c - '0' & 1;
      ans = (ans * 10 + maxHeap[i].poll());
    }

    return ans;
  }
}
// code provided by PROGIEZ

2231. Largest Number After Digit Swaps by Parity LeetCode Solution in Python

class Solution:
  def largestInteger(self, num: int) -> int:
    s = str(num)
    ans = 0
    # maxHeap[0] := the odd digits
    # maxHeap[1] := the even digits
    maxHeap = [[] for _ in range(2)]

    for c in s:
      digit = int(c)
      heapq.heappush(maxHeap[digit % 2], -digit)

    for c in s:
      i = int(c) & 1
      ans = (ans * 10 - heapq.heappop(maxHeap[i]))

    return ans
 # code by PROGIEZ