Skip to content

2231. Largest Number After Digit Swaps by Parity

  • Time: $O(\log\texttt{num})$
  • Space: $O(\log\texttt{num})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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