Split With Minimum Sum

🏠 ⬅️ ➡️

Given a positive integer num, split it into two non-negative integers num1 and num2 such that:

  • The concatenation of num1 and num2 is a permutation of num.
    • In other words, the sum of the number of occurrences of each digit in num1 and num2 is equal to the number of occurrences of that digit in num.
  • num1 and num2 can contain leading zeros.

Return the minimum possible sum of num1 and num2.

Notes:

  • It is guaranteed that num does not contain any leading zeros.
  • The order of occurrence of the digits in num1 and num2 may differ from the order of occurrence of num.

Example 1:

Input: num = 4325 Output: 59 Explanation: We can split 4325 so that num1 is 24 and num2 is 35, giving a sum of 59. We can prove that 59 is indeed the minimal possible sum.

Example 2:

Input: num = 687 Output: 75 Explanation: We can split 687 so that num1 is 68 and num2 is 7, which would give an optimal sum of 75.

Constraints:

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

    integer :: num, num1, num2, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
    character(len=10) :: str

    ! Examples
    num = 4325
    call solve(num, num1, num2)
    write (*, '(A, I0, A, I0)') 'Minimum sum: ', num1 + num2, ' (', num1, ', ', num2, ')'

    num = 687
    call solve(num, num1, num2)
    write (*, '(A, I0, A, I0)') 'Minimum sum: ', num1 + num2, ' (', num1, ', ', num2, ')'

contains

    subroutine solve(num, num1, num2)
        implicit none
        integer, intent(in) :: num
        integer, intent(out) :: num1, num2
        integer :: count(10), perm(10), tmp(10)

        ! Initialize counts for each digit
        do i = 1, 10
            count(i) = 0
        end do

        ! Count the number of occurrences of each digit in num
        do i = 1, len_trim(str(num))
            count(ichar(str(num)(i:i))) = count(ichar(str(num)(i:i))) + 1
        end do

        ! Generate a permutation of the digits
        perm(:) = (/ (j, j=1,10) /)
        call shuffle(perm)

        ! Find the first digit that has a count greater than its position in the permutation
        do i = 1, 10
            if (count(perm(i)) > i) then
                exit
            end if
        end do

        ! If no such digit exists, return 0
        if (i == 11) then
            num1 = 0
            num2 = 0
            return
        end if

        ! Set num1 to the first digit
        num1 = perm(i)

        ! Remove the first digit from the count array
        count(perm(i)) = 0

        ! Find the next digit that has a count greater than its position in the permutation
        do j = i + 1, 10
            if (count(perm(j)) > j) then
                exit
            end if
        end do

        ! If no such digit exists, return 0
        if (j == 11) then
            num1 = 0
            num2 = 0
            return
        end if

        ! Set num2 to the second digit
        num2 = perm(j)

        ! Remove the second digit from the count array
        count(perm(j)) = 0

        ! Find the third digit that has a count greater than its position in the permutation
        do k = j + 1, 10
            if (count(perm(k)) > k) then
                exit
            end if
        end do

        ! If no such digit exists, return 0
        if (k == 11) then
            num1 = 0
            num2 = 0
            return
        end if

        ! Set num3 to the third digit
        num3 = perm(k)

        ! Remove the third digit from the count array
        count(perm(k)) = 0

        ! Find the fourth digit that has a count greater than its position in the permutation
        do l = k + 1, 10
            if (count(perm(l)) > l) then
                exit
            end if
        end do

        ! If no such digit exists, return 0
        if (l == 11) then
            num1 = 0
            num2 = 0
            return
        end if

        ! Set num4 to the fourth digit
        num4 = perm(l)

        ! Remove the fourth digit from the count array
        count(perm(l)) = 0

        ! Find the fifth digit that has a count greater than its position in the permutation
        do m = l + 1, 10
            if
✅ Compiled
❌ Executed
❌ Correct 
! This is a full Fortran script with a valid main entry point that solves the problem.

program split_num
implicit none

! Declare the variables
integer :: num, num1, num2, i, j, count, sum
character(len=10) :: num_str

! Read the input
read(*,*) num

! Convert the input to a string
write(num_str,*) num

! Initialize the variables
num1 = 0
num2 = 0
sum = 0

! Loop through each digit in the input
do i = 1, len_trim(num_str)
    ! Get the current digit
    j = ichar(num_str(i:i)) - ichar('0')

    ! Increment the count of the current digit
    count = count + 1

    ! Check if the current digit is in the first half of the input
    if (i <= len_trim(num_str)/2) then
        ! Increment the sum
        sum = sum + count

        ! Increment the first half of the input
        num1 = num1 * 10 + j
    else
        ! Increment the second half of the input
        num2 = num2 * 10 + j
    end if
end do

! Print the output
write(*,*) sum

end program split_num
🌐 Data from online sources 
def min_sum_of_two_numbers(num: str) -> int:
    cnt = [0] * 10
    for c in num:
        cnt[int(c)] += 1

    num1, num2 = 0, 0
    for i in range(1, 10, 2):
        temp = cnt[i]
        while temp > 0:
            num1 = num1 * 10 + i
            temp -= 1
    for i in range(0, 10, 2):
        temp = cnt[i]
        while temp > 0:
            num2 = num2 * 10 + i
            temp -= 1
    return num1 + num2

The algorithm first creates a frequency count of each digit in the given number. Then, it initializes two variables representing num1 and num2. Next, the algorithm iterates through the frequency count array, adding all odd digits to num1 and all even digits to num2. Finally, the algorithm returns the sum of num1 and num2.

Note that the algorithm for each language is quite similar, with minor variations in syntax or the ways to compute the counts.

🌐 Data from online sources 
int minSumOfTwoNumbers(string num) {
    vector<int> cnt(10, 0);
    for (char c : num) 
        cnt[c - '0']++;

    int num1 = 0, num2 = 0;
    for (int i = 1; i <= 9; i += 2) {
        int temp = cnt[i];
        while (temp--)
            num1 = num1 * 10 + i;
    }
    for (int i = 0; i <= 9; i += 2) {
        int temp = cnt[i];
        while (temp--)
            num2 = num2 * 10 + i;
    }
    return num1 + num2;
}

The algorithm first creates a frequency count of each digit in the given number. Then, it initializes two variables representing num1 and num2. Next, the algorithm iterates through the frequency count array, adding all odd digits to num1 and all even digits to num2. Finally, the algorithm returns the sum of num1 and num2.

Note that the algorithm for each language is quite similar, with minor variations in syntax or the ways to compute the counts.