algoadvance

Leetcode 2231. Largest Number After Digit Swaps by Parity

Problem Statement

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 performing any number of swaps.

Example 1:

Input: num = 1234
Output: 3412
Explanation: Swap the digit 3 and the digit 1, and swap the digit 4 and the digit 2.

Example 2:

Input: num = 65875
Output: 87655
Explanation: Swap the digit 8 and the digit 6, and swap the digit 7 and the digit 5.

Clarifying Questions

  1. What is the range of the input number?
    • The input number will be a positive integer generally within the range of typical Java integers.
  2. Can input numbers have leading zeros after swaps?
    • No, leading zeros are not considered since the number is positive and leading zeros do not make sense in this context.

Strategy

  1. Digit Classification by Parity: First, we classify digits of num into two lists: one for even digits and one for odd digits.
  2. Sorting: Sort the even and odd lists in descending order.
  3. Reconstruction of Number: Iterate over the original number and replace each digit with the next largest available digit from its respective parity list.
  4. Concatenate and Convert: Convert the reconstructed list back to an integer.

Code

public class LargestNumberByParitySwap {

    public static int largestInteger(int num) {
        // Convert number to string for easy digit manipulation
        String numStr = Integer.toString(num);
        char[] digits = numStr.toCharArray();
        
        // Lists to hold even and odd digits
        List<Character> evens = new ArrayList<>();
        List<Character> odds = new ArrayList<>();
        
        // Separate digits into even and odd lists
        for (char digit : digits) {
            if ((digit - '0') % 2 == 0) {
                evens.add(digit);
            } else {
                odds.add(digit);
            }
        }
        
        // Sort the lists in descending order
        Collections.sort(evens, Collections.reverseOrder());
        Collections.sort(odds, Collections.reverseOrder());
        
        // Indices to keep track of current position in the sorted lists
        int evenIndex = 0;
        int oddIndex = 0;
        
        // Resultant array to construct the largest number
        char[] result = new char[digits.length];
        
        // Fill the resultant array with the largest possible digits of correct parity
        for (int i = 0; i < digits.length; i++) {
            if ((digits[i] - '0') % 2 == 0) {
                result[i] = evens.get(evenIndex++);
            } else {
                result[i] = odds.get(oddIndex++);
            }
        }
        
        // Convert the result array back to an integer
        return Integer.parseInt(new String(result));
    }
    
    public static void main(String[] args) {
        // Test cases
        System.out.println(largestInteger(1234));  // Output: 3412
        System.out.println(largestInteger(65875)); // Output: 87655
    }
}

Time Complexity

Overall Time Complexity: O(n log n)

This approach ensures that the result is constructed in the largest possible manner by considering parity-based swaps while ensuring efficiency.

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