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

Return the largest possible value of num after any number of swaps.

Example 1:

Input: num = 1234 Output: 3412 Explanation: Swap the digit 3 with the digit 1, this results in the number 3214. Swap the digit 2 with the digit 4, this results in the number 3412. Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number. Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.

Example 2:

Input: num = 65875 Output: 87655 Explanation: Swap the digit 8 with the digit 6, this results in the number 85675. Swap the first digit 5 with the digit 7, this results in the number 87655. Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.

Constraints:

  • 1 <= num <= 109
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: num

    print '(A)', solve(1234)
    print '(A)', solve(65875)

contains

    function solve(num) result(max_value)
        implicit none
        integer, intent(in) :: num
        integer :: max_value
        integer :: i, j, temp

        do i = 1, len(num) - 1
            do j = i + 1, len(num)
                if (mod(num(i), 2) == mod(num(j), 2)) then
                    temp = num(i)
                    num(i) = num(j)
                    num(j) = temp
                end if
            end do
        end do

        max_value = num
    end function solve
end program main
❌ Compiled
❌ Executed
❌ Correct 
PROGRAM LARGEST_NUMBER
      IMPLICIT NONE

      INTEGER, PARAMETER :: MAX_NUM = 109
      INTEGER :: num, max_num, i, j, temp

      READ(*,*) num

      max_num = num

      DO i = 1, MAX_NUM
         DO j = i + 1, MAX_NUM
            IF (MOD(num, i) == MOD(num, j)) THEN
               temp = num / 10**(i-1)
               temp = temp - (temp / 10) * 10
               temp = temp + (temp / 10) * 10
               num = num - temp * 10**(i-1) + temp * 10**(j-1)
               max_num = MAX(max_num, num)
            END IF
         END DO
      END DO

      WRITE(*,*) max_num

      END PROGRAM LARGEST_NUMBER

This script uses a brute force approach to solve the problem. It iterates through all possible swaps of digits in the input number, and checks if the resulting number is larger than the current largest number. If it is, it updates the largest number. The script uses the `MOD` function to check if two digits have the same parity, and the `MAX` function to compare and update the largest number.

The script uses the `IMPLICIT NONE` statement to disable the use of implicit typing, and the `PARAMETER` statement to define a constant for the maximum value of the input number.

The script reads the input number from the standard input, and stores it in the `num` variable. It then initializes the `max_num` variable to the input number, and starts the brute force search for the largest possible number.

The script uses a nested loop to iterate through all possible swaps of digits in the input number. The outer loop iterates through the digits of the input number, and the inner loop iterates through the remaining digits of the input number. The `IF` statement checks if the two digits have the same parity, and if they do, it swaps them and updates the `num` variable. The `MAX` function is used to compare and update the largest number.

The script writes the largest possible number to the standard output.

Note that this script assumes that the input number is a positive integer between 1 and 109, inclusive. If the input number is outside of this range, the script will not work correctly.
🌐 Data from online sources 
def first_palindrome(words):
    for word in words:
        if word == word[::-1]:
            return word
    return ""

The algorithm used in each function iterates through the given array of strings, and for each string, it checks if it's a palindrome by comparing it to its reversed version. If a palindrome is found, it immediately returns that string. If no palindromes are found after iterating through the entire array, an empty string is returned. Each language's implementation follows similar logic, with some differences:
  • C++: We use a range-based loop to iterate through the words, and the std::reverse() function to reverse the string.
  • Java: We use a StringBuilder to reverse the string, and the equals() method to compare the strings.
  • Python: A Pythonic approach is used with slicing to reverse the string.
  • JavaScript: We use the split(), reverse(), and join() methods to reverse the string.
🌐 Data from online sources 
#include <string>
#include <vector>

std::string firstPalindrome(const std::vector<std::string>& words) {
    for (const std::string& word : words) {
        std::string reversedWord = word;
        std::reverse(reversedWord.begin(), reversedWord.end());
        if (word == reversedWord) {
            return word;
        }
    }
    return "";
}

The algorithm used in each function iterates through the given array of strings, and for each string, it checks if it's a palindrome by comparing it to its reversed version. If a palindrome is found, it immediately returns that string. If no palindromes are found after iterating through the entire array, an empty string is returned. Each language's implementation follows similar logic, with some differences:
  • C++: We use a range-based loop to iterate through the words, and the std::reverse() function to reverse the string.
  • Java: We use a StringBuilder to reverse the string, and the equals() method to compare the strings.
  • Python: A Pythonic approach is used with slicing to reverse the string.
  • JavaScript: We use the split(), reverse(), and join() methods to reverse the string.