Leetcode 2231: Largest Number After Digit Swaps by Parity
You are given a positive integer
num. You are allowed to swap any two digits of num that have the same parity (i.e., both digits are either odd or both even). The goal is to return the largest possible value of num after any number of swaps.Problem
Approach
Steps
Complexity
Input: The input consists of a positive integer `num`.
Example: num = 8235
Constraints:
• 1 <= num <= 10^9
Output: Return the largest possible value of `num` after performing any number of valid swaps.
Example: Output: 8532
Constraints:
• The result will be a positive integer.
Goal: The goal is to maximize the number by swapping digits of the same parity. To achieve this, we will use priority queues to store the odd and even digits in descending order and then place the largest possible digits at their respective positions.
Steps:
• 1. Convert the number into a string to easily access each digit.
• 2. Separate the odd and even digits into two different priority queues, ensuring the digits are stored in descending order.
• 3. For each digit in the original number, replace it with the largest available odd or even digit from the respective priority queue, depending on its parity.
Goal: The solution must handle up to 9 digits in `num` efficiently.
Steps:
• The number `num` will have at most 9 digits.
Assumptions:
• The input is always a valid positive integer.
• Input: Input: num = 8235
• Explanation: In this case, we have two even digits (8, 2) and two odd digits (3, 5). After sorting both even and odd digits in descending order, we get 8, 2 for evens and 5, 3 for odds. Swapping the digits gives the largest possible number: 8532.
• Input: Input: num = 4321
• Explanation: Here, we have two even digits (4, 2) and two odd digits (3, 1). After sorting, we get 4, 2 for evens and 3, 1 for odds. Swapping the digits to maximize the value results in 4321, which is already the largest possible number.
Approach: The approach involves using priority queues (heaps) to rearrange the digits in such a way that maximizes the number. We separate the even and odd digits, store them in descending order, and then reconstruct the number by assigning the largest available digits to each place.
Observations:
• Sorting the digits by parity allows us to focus on the largest possible number for each set of digits.
• The problem can be solved by treating it as a sorting problem for two distinct groups of digits: even and odd.
Steps:
• 1. Convert the number `num` into a string to work with its individual digits.
• 2. Separate the digits into two priority queues: one for even digits and one for odd digits.
• 3. Sort the even and odd digits in descending order using the priority queues.
• 4. Rebuild the number by replacing each digit with the largest available digit from the corresponding queue.
Empty Inputs:
• There are no empty inputs as the problem guarantees that `num` is always a positive integer.
Large Inputs:
• The input will not exceed 9 digits, so the solution should efficiently handle the maximum size.
Special Values:
• If `num` consists of only even or only odd digits, the number is already the largest possible number.
Constraints:
• The solution must handle cases where all digits have the same parity.
int largestInteger(int num) {
priority_queue<int> p; // priority queue to store odd digits in descending order
priority_queue<int> q; // priority queue to store even digits in descending order
string nums=to_string(num); // converting num to a string for easy access of the digits
int n=nums.size(); // n stores the number of digits in num
for(int i=0;i<n;i++){
int digit=nums[i]-'0';
if((digit)%2) // if digit is odd, push it into priority queue p
p.push(digit);
else
q.push(digit); // if digit is even, push it into priority queue q
}
int answer=0;
for(int i=0; i<n; i++){
answer=answer*10;
if((nums[i]-'0')%2) // if the digit is odd, add the largest odd digit of p into the answer
{answer+=p.top();p.pop();}
else
{answer+=q.top();q.pop();} // if the digit is even, add the largest even digit of q into the answer
}
return answer;
}
1 : Function Declaration
int largestInteger(int num) {
The function `largestInteger` is declared, taking an integer `num` as input and returning an integer as the output.
2 : Priority Queue Declaration
priority_queue<int> p; // priority queue to store odd digits in descending order
A priority queue `p` is declared to store the odd digits from `num` in descending order.
3 : Priority Queue Declaration
priority_queue<int> q; // priority queue to store even digits in descending order
Another priority queue `q` is declared to store the even digits from `num` in descending order.
4 : String Conversion
string nums=to_string(num); // converting num to a string for easy access of the digits
The integer `num` is converted into a string `nums` for easier access to its individual digits.
5 : Variable Initialization
int n=nums.size(); // n stores the number of digits in num
The variable `n` is initialized to the size of the string `nums`, representing the number of digits in the input number.
6 : For Loop
for(int i=0;i<n;i++){
A `for` loop is initiated to iterate through each character (digit) of the string `nums`.
7 : Digit Extraction
int digit=nums[i]-'0';
Each character in the string `nums` is converted back to an integer `digit`.
8 : Condition Check
if((digit)%2) // if digit is odd, push it into priority queue p
A condition checks if the current digit is odd by checking if the digit modulo 2 is non-zero.
9 : Priority Queue Insert
p.push(digit);
If the digit is odd, it is pushed into the priority queue `p`.
10 : Else Statement
else
If the digit is not odd (i.e., it is even), the following code block will execute.
11 : Priority Queue Insert
q.push(digit); // if digit is even, push it into priority queue q
If the digit is even, it is pushed into the priority queue `q`.
12 : Variable Initialization
int answer=0;
A variable `answer` is initialized to 0, which will store the final rearranged number.
13 : For Loop
for(int i=0; i<n; i++){
A second `for` loop is initiated to reconstruct the number based on the priority queues.
14 : Answer Calculation
answer=answer*10;
The variable `answer` is updated by multiplying the current value by 10, making space for the next digit.
15 : Condition Check
if((nums[i]-'0')%2) // if the digit is odd, add the largest odd digit of p into the answer
A condition checks if the current digit in `nums` is odd. If it is, the largest odd digit from `p` will be added to `answer`.
16 : Priority Queue Pop
{answer+=p.top();p.pop();}
If the digit is odd, the top element from priority queue `p` (largest odd digit) is added to `answer` and popped from the queue.
17 : Else Statement
else
If the digit is even, the following code block will execute.
18 : Priority Queue Pop
{answer+=q.top();q.pop();} // if the digit is even, add the largest even digit of q into the answer
If the digit is even, the top element from priority queue `q` (largest even digit) is added to `answer` and popped from the queue.
19 : Return Statement
return answer;
The function returns the final rearranged number `answer`.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The sorting of digits in the priority queues dominates the time complexity, where `n` is the number of digits in `num`.
Best Case: O(n)
Worst Case: O(n)
Description: We use space for storing the even and odd digits, which requires O(n) space where `n` is the number of digits in `num`.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus