Largest Number After Digit Swaps by Parity

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def largestInteger(self, n: int) -> int:
        a = list(str(n))  # Convert integer to list of characters (digits)

        for i in range(len(a)):
            for j in range(i + 1, len(a)):
                # Check if a[j] is larger than a[i] and they have the same parity
                if a[j] > a[i] and (int(a[j]) - int(a[i])) % 2 == 0:
                    # Swap a[i] and a[j]
                    a[i], a[j] = a[j], a[i]

        return int(''.join(a))  # Convert list of digits back to integer

This function, largestInteger, is intended to rearrange the digits of a given integer n to create the largest possible number, with the additional condition that the swapped digits must have the same parity (i.e., both are odd or both are even).

Here’s a detailed breakdown of the code:

  1. It first converts the integer n into a list of characters a using list(str(n)).

  2. It then performs a nested loop over the list of characters a. For each pair of digits at positions i and j (j > i), it checks the following:

    • If the digit at j is greater than the digit at i and the difference between these two digits is even. The parity check (int(a[j]) - int(a[i])) % 2 == 0 is basically checking whether both digits are odd or both are even.

    • If these conditions are satisfied, it swaps the digits at positions i and j in the list a.

  3. After all possible pairs of digits have been considered and the necessary swaps have been made, the function converts the list a back into an integer by joining the characters together and converting the resulting string back into an integer.

The time complexity of this function is O(n^2), where n is the number of digits in the input integer. This is because the function performs a nested loop over the digits. The space complexity is O(n), for storing the digits in the list a.

Note: This function assumes that n is a non-negative integer. If n can be negative, additional handling would be needed.

Q&A

Does the solution look like bubble sort?

Yes, the approach used in this solution does bear some resemblance to the Bubble Sort algorithm, but with an additional condition for swapping elements.

In Bubble Sort, we iterate through the list multiple times, and in each pass, we compare each pair of adjacent elements and swap them if they are in the wrong order. By doing this repeatedly, the largest (or smallest, depending on the order) elements “bubble” their way to the end of the list, hence the name “Bubble Sort”.

In the provided solution, we also have nested loops that iterate through the list of digits. But instead of simply swapping adjacent elements that are out of order, we have an additional condition: the two digits must have the same parity (i.e., both are even or both are odd), and the digit at the higher index is greater than the one at the lower index.

So, while this isn’t exactly Bubble Sort, it uses a similar concept of comparing and potentially swapping elements in a list in a nested loop. This similarity is part of what makes this solution an interesting variant on a familiar algorithmic pattern.