2231. Largest Number After Digit Swaps by Parity

Problem Description

In this problem, we are provided with a positive integer num and we're allowed to swap the digits of num under one condition: the swapped digits must have the same parity – meaning they are either both odd numbers or both even numbers. Our task is to find the maximal value of num that can be achieved through any number of such swaps.

Intuition

The key to solving this problem is to realize that the highest value of a number is obtained when its digits are sorted in non-increasing order from left to right. However, because we can only swap digits of the same parity, we need to handle even and odd digits separately.

The strategy is this:

Store the frequency (count) of each digit of num. This helps us keep track of how many times we can use each digit in the reconstruction of the largest possible number.
Iterate over the digits of num starting from the least significant digit (rightmost digit).
For each digit, we check if there is a larger digit of the same parity that we have not used yet (using our frequency count from step 1). If so, we place that larger digit in the current position to build the largest number.
We repeat this process for every digit, thereby creating the largest number possible under the constraint that we can only swap digits of the same parity.

The solution code provided uses a Counter from the collections module to keep track of the digit frequencies. By iterating over the digits and selecting the largest possible same-parity digit we have available each time, it constructs the solution effectively.

Learn more about Sorting and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The code implements the strategy described in the intuition by following these steps:

It starts by creating a Counter from Python's collections module, which is used as a hash map to store the frequency of each digit in the original number.
Then, the code iterates over the provided number num to populate the Counter with the correct frequencies of the digits.
With the Counter initialized, the solution iterates through the digits of num again, this time extracting each digit starting from the least significant digit (rightmost digit).
The extracted digit is compared against all available digits in descending order (from 9 to 0) to find a digit of the same parity that is greater and still available for swapping (based on the frequency stored in the Counter).
The ((v ^ y) & 1) comparison is used to check if the current digit v and the potential digit y have the same parity. The XOR operator ^ gives 0 when both numbers have the same parity, and the bitwise AND with 1, & 1, filters the result to keep only even comparisons, ensuring parity is maintained.
Once a suitable digit y is found, it is placed at the current position in the answer by adding y * t to ans, where t is the positional value (1 for the unit's place, 10 for the ten's place, etc.). After a digit is used, its count in the Counter is decremented.
The loop continues until all digits of the original number have been replaced, building up the largest number possible digit by digit.
Finally, the function returns ans, which is the largest integer we can get after making all possible parity-preserving digit swaps in the initial number num.

This solution intelligently combines the Counter data structure with bitwise operations to ensure that swaps only occur between digits with the same parity and greedily selects the largest possible digit for each place value.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

Example Walkthrough

Let's consider the number num = 2736 and walk through the solution approach to find the maximal number that can be achieved through swapping digits of the same parity.

Create a Counter to store the frequency of each digit. For num = 2736, the counter would be {2: 1, 7: 1, 3: 1, 6: 1}.
Iterate over the digits of num starting from the least significant digit. We will process the digits in this order: 6, 3, 7, 2.
Starting with the rightmost digit 6, we look for the largest even digit available for swap—we can swap it with 2 which is the only even digit smaller than 6. However, since 6 is already the largest even digit, we leave it as it is.
Move to the next digit 3, an odd digit. The only odd digit larger than 3 available for swap is 7. Thus, we swap 3 with 7. Now our number looks like 2763.
Next, we look at 7. There are no digits larger than 7 that are odd, so we leave it as it is.
Finally, we move to the leftmost digit 2. Since we cannot increase the value of 2 through any even-swaps (6 is already at the rightmost position), we leave it as it is.
Continuing until all digits are checked, we have successfully transformed 2736 into 2763 by making the swap of 3 with 7.
The resulting maximal number is 2763, which is returned as the solution.

This example demonstrates how, by using a Counter to track digits and iterating from right to left to find the highest digit swap of the same parity, we can construct the largest possible number under the parity swap rule. The process emphasizes greedily selecting the best digit for each position while maintaining the condition of parity.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def largestInteger(self, num: int) -> int:
5        # Create a counter to track the frequency of digits in the number
6        digit_counter = Counter()
7      
8        # Extract each digit and update its count in the counter
9        temp = num
10        while temp:
11            temp, digit = divmod(temp, 10)
12            digit_counter[digit] += 1
13      
14        # Initialize variables to construct the largest number
15        temp = num
16        largest_number = 0
17        place_value = 1  # Used to construct the number digit by digit
18      
19        # Construct the largest number with the same even/oddness of digits
20        while temp:
21            # Extract the rightmost digit from the remaining number
22            temp, digit = divmod(temp, 10)
23          
24            # Try to find the largest digit with the same even/oddness
25            for larger_digit in range(9, -1, -1):
26                # Check if both have the same even/oddness by using XOR and if the digit is available
27                if ((digit ^ larger_digit) & 1) == 0 and digit_counter[larger_digit] > 0:
28                    # Append the largest digit at the current place value
29                    largest_number += larger_digit * place_value
30                    # Update the place value for the next digit
31                    place_value *= 10
32                    # Decrease the count of used digit in the counter
33                    digit_counter[larger_digit] -= 1
34                    break  # Exit the loop after finding the largest suitable digit
35      
36        return largest_number
37

1class Solution {
2    public int largestInteger(int num) {
3        // Array to count the occurrences of each digit in the number
4        int[] digitCounts = new int[10];
5        int tempNum = num; // Temporary variable to manipulate the number without altering the original
6      
7        // Count occurrences of each digit
8        while (tempNum != 0) {
9            digitCounts[tempNum % 10]++;
10            tempNum /= 10;
11        }
12      
13        tempNum = num; // Reset tempNum to original number
14        int result = 0;  // This will store the resulting largest integer
15        int placeValue = 1; // Used to reconstruct the number by adding digits at the correct place value
16
17        // Iterate over each digit in the number
18        while (tempNum != 0) {
19            int currentDigit = tempNum % 10; // Current digit of the number from right to left
20            tempNum /= 10; // Remove the current digit from tempNum
21          
22            // Look for the largest digit not yet used that has the same parity (odd/even) as currentDigit
23            for (int nextDigit = 9; nextDigit >= 0; --nextDigit) {
24                // Check if 'nextDigit' has the same parity as 'currentDigit' and if it's available
25                if (((currentDigit ^ nextDigit) & 1) == 0 && digitCounts[nextDigit] > 0) {
26                    digitCounts[nextDigit]--; // Decrease count of the digit as it's now used
27                    result += nextDigit * placeValue; // Add digit at correct place value to result
28                    placeValue *= 10; // Increase place value for the next iteration
29                    break; // Break since we have found the largest digit with same parity
30                }
31            }
32        }
33      
34        return result; // Return the result
35    }
36}
37

1#include <vector> // Include the vector header for using the vector container
2using namespace std;
3
4class Solution {
5public:
6    // Function to calculate the largest integer formed by swapping digits with same parity
7    int largestInteger(int num) {
8        vector<int> digitCount(10, 0); // Create a count array initialized to 0 for digits 0-9
9        int tempNum = num; // Temporary variable to process the number
10
11        // Count the occurrence of each digit in the number
12        while (tempNum > 0) {
13            digitCount[tempNum % 10]++;
14            tempNum /= 10;
15        }
16
17        tempNum = num; // Reset tempNum to process the number again
18        int answer = 0; // Initialize the answer which will store the largest integer
19        long multiplier = 1; // Initialize the multiplier for the current digit position
20
21        // Construct the largest integer by picking the largest digits that have the same parity
22        while (tempNum > 0) {
23            int currentDigit = tempNum % 10; // Extract the least significant digit
24            tempNum /= 10; // Remove the least significant digit from tempNum
25
26            // Loop to find the largest digit of the same parity
27            for (int newDigit = 9; newDigit >= 0; --newDigit) {
28                // Check if the newDigit has the same parity as currentDigit and is available (count > 0)
29                if ((currentDigit % 2 == newDigit % 2) && digitCount[newDigit] > 0) {
30                    digitCount[newDigit]--; // Decrement the count since we're using this digit
31                    answer += newDigit * multiplier; // Add the digit to the answer in correct position
32                    multiplier *= 10; // Move to the next digit position
33                    break; // Break since we found the largest digit of the same parity
34                }
35            }
36        }
37        return answer; // Return the answer after processing the entire number
38    }
39};
40

1function largestInteger(num: number): number {
2    // Convert the given number to an array of its digits.
3    let digits = String(num).split('').map(Number);
4
5    // Arrays to hold the odd and even digits separately.
6    let oddDigits: number[] = [];
7    let evenDigits: number[] = [];
8
9    // Iterate over each digit and classify them into odd or even.
10    for (let digit of digits) {
11        if (digit % 2 === 1) {
12            oddDigits.push(digit);
13        } else {
14            evenDigits.push(digit);
15        }
16    }
17
18    // Sort the odd and even digits arrays in ascending order.
19    oddDigits.sort((a, b) => a - b);
20    evenDigits.sort((a, b) => a - b);
21
22    // Array to hold the rearranged largest integer.
23    let largestIntDigits: number[] = [];
24
25    // Construct the largest integer by selecting the largest available odd or even digit.
26    for (let digit of digits) {
27        if (digit % 2 === 1) {
28            // For odd digits, pop the largest remaining odd digit.
29            largestIntDigits.push(oddDigits.pop()!); // Using non-null assertion since we are sure the array is not empty.
30        } else {
31            // For even digits, pop the largest remaining even digit.
32            largestIntDigits.push(evenDigits.pop()!); // Same non-null assertion applies here.
33        }
34    }
35
36    // Convert the array of digits back to a number and return.
37    return Number(largestIntDigits.join(''));
38}
39

Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First SearchBreadth First Search

I don’t know

Time and Space Complexity

Time Complexity

The given code consists of the following operations:

A while loop to count the digits (using Counter) of the input number num. This loop runs as many times as there are digits in num. The number of digits in a number is given by O(log(n)), where n is the input number.
Another while loop that also runs once for every digit in num. Within this loop, there's a for loop that could run up to 10 times (the digits 0 through 9) for each digit in the original number to find the largest digit with the same parity (odd or even) that hasn't been used yet.

Therefore, the overall time complexity of the code is governed by these nested loops, giving us:

Outer loop: O(log(n)) for the number of digits.
Inner loop: O(1) since it's a constant run of up to 10.

Hence, the combined time complexity is O(10 * log(n)), which simplifies to O(log(n)) since constant factors are dropped in Big O notation.

Space Complexity

The space complexity is determined by the additional space used by the algorithm:

Counter used to store the frequency of each digit. In the worst case, we store 10 key-value pairs, one for each digit from 0 to 9, so this uses O(1) space.
Constant amount of extra space used for variables x, v, ans, and t.

Thus, the overall space complexity of the code is O(1), as it uses constant extra space regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2231. Largest Number After Digit Swaps by Parity

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings