algoadvance

Leetcode 2231. Largest Number After Digit Swaps by Parity

Problem Statement

2231. 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 are odd digits or both are even digits).

Return the largest possible value of num you can get by swapping any two digits with the same parity.

Clarifying Questions

1. Input Range: What is the range of the positive integer num?
   • Answer: num is a positive integer, so it ranges from 1 up to 10^9.
2. Output Format: Should the output be in the form of an integer or a string (if leading zeroes are relevant)?
   • Answer: The output should be an integer, as swaps will not create leading zeros.
3. Swaps Involving Parity: Can I clarify that we can only swap even digits with even digits and odd digits with odd digits?
   • Answer: Yes, that is correct. Swaps are allowed only between digits of the same parity.

Strategy

1. Extract Even and Odd Digits: Separate the digits of num into even digits and odd digits. Store their positions and values.

2. Sort Digits: Sort the even digits in descending order and do the same for odd digits. This ensures that we can place the largest possible digits in leading positions.

3. Reconstruct the Number: Reconstruct the number by replacing the original positions with the largest possible digits from our sorted lists.

Time Complexity

• Sorting: Sorting the digits will take (O(k \log k)), where (k) is the number of even/odd digits (at most 9 since the maximum number of digits in num is 9 for (10^9)).
• Overall Complexity: Thus, the overall time complexity is (O(9 \log 9)), which simplifies to (O(1)) considering constant maximum digits.

Code Implementation

#include <vector>
#include <algorithm>
#include <string>
#include <iostream>

int largestInteger(int num) {
    std::string numStr = std::to_string(num);
    std::vector<int> oddDigits, evenDigits;

    // Separate odd and even digits.
    for (char digit : numStr) {
        if ((digit - '0') % 2 == 0) {
            evenDigits.push_back(digit - '0');
        } else {
            oddDigits.push_back(digit - '0');
        }
    }

    // Sort digits in descending order.
    std::sort(evenDigits.begin(), evenDigits.end(), std::greater<int>());
    std::sort(oddDigits.begin(), oddDigits.end(), std::greater<int>());

    // Reconstruct the number
    std::string resultStr = numStr;
    int evenIndex = 0, oddIndex = 0;

    for (char& digit : resultStr) {
        if ((digit - '0') % 2 == 0) {
            digit = evenDigits[evenIndex++] + '0';
        } else {
            digit = oddDigits[oddIndex++] + '0';
        }
    }

    return std::stoi(resultStr);
}

int main() {
    int num = 1234;
    std::cout << largestInteger(num) << std::endl;  // Output: 3412
    return 0;
}

Explanation

1. Separation of Digits: Iterate through each digit of the number and separate them into even and odd lists.

2. Sorting: Sort both lists in descending order to maximize the value.

3. Reconstruction: Rebuild the number by replacing each digit with the largest possible digit from the sorted lists while maintaining parity.

This method ensures that swapping results in the largest possible number by adhering to the parity swapping constraint.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?