Minimum Sum of Four Digit Number After Splitting Digits

🏠 ⬅️ ➡️

You are given a positive integer num consisting of exactly four digits. Split num into two new integers new1 and new2 by using the digits found in num. Leading zeros are allowed in new1 and new2, and all the digits found in num must be used.

  • For example, given num = 2932, you have the following digits: two 2's, one 9 and one 3. Some of the possible pairs [new1, new2] are [22, 93], [23, 92], [223, 9] and [2, 329].

Return the minimum possible sum of new1 and new2.

Example 1:

Input: num = 2932 Output: 52 Explanation: Some possible pairs [new1, new2] are [29, 23], [223, 9], etc. The minimum sum can be obtained by the pair [29, 23]: 29 + 23 = 52.

Example 2:

Input: num = 4009 Output: 13 Explanation: Some possible pairs [new1, new2] are [0, 49], [490, 0], etc. The minimum sum can be obtained by the pair [4, 9]: 4 + 9 = 13.

Constraints:

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

    integer :: num, new1, new2, min_sum

    ! Examples
    num = 2932
    call solve(num, new1, new2, min_sum)
    write (*, '(A, I0, A, I0, A, I0)') 'Example 1: ', &
        num, ' -> ', new1, ' + ', new2, ' = ', min_sum

    num = 4009
    call solve(num, new1, new2, min_sum)
    write (*, '(A, I0, A, I0, A, I0)') 'Example 2: ', &
        num, ' -> ', new1, ' + ', new2, ' = ', min_sum

contains

    subroutine solve(num, new1, new2, min_sum)
        implicit none
        integer, intent(in) :: num
        integer, intent(out) :: new1, new2, min_sum

        integer :: i, j, k, l
        integer :: digit1, digit2, digit3, digit4
        logical :: found

        found = .false.
        min_sum = huge(min_sum)

        do i = 1, 9
            digit1 = mod(num, 10)
            if (digit1 == 0) then
                cycle
            end if
            num = num / 10

            do j = 1, 9
                digit2 = mod(num, 10)
                if (digit2 == 0) then
                    cycle
                end if
                num = num / 10

                do k = 1, 9
                    digit3 = mod(num, 10)
                    if (digit3 == 0) then
                        cycle
                    end if
                    num = num / 10

                    do l = 1, 9
                        digit4 = mod(num, 10)
                        if (digit4 == 0) then
                            cycle
                        end if
                        num = num / 10

                        if (i == digit1 .or. j == digit2 .or. k == digit3 .or. l == digit4) then
                            found = .true.
                            exit
                        end if

                    end do

                    if (found) then
                        exit
                    end if

                end do

                if (found) then
                    exit
                end if

            end do

            if (found) then
                exit
            end if

        end do

        if (.not. found) then
            stop "No solution"
        end if

        new1 = i * 1000 + j * 100 + k * 10 + l
        new2 = digit1 * 1000 + digit2 * 100 + digit3 * 10 + digit4
        min_sum = min(min_sum, new1 + new2)

    end subroutine solve

end program main
✅ Compiled
❌ Executed
❌ Correct 
!--------------------------------------------------------------------------------
! This is a Fortran implementation of the problem statement.
!
! The program takes a positive integer num consisting of exactly four digits
! as input. It splits num into two new integers new1 and new2 by using the
! digits found in num. Leading zeros are allowed in new1 and new2, and all the
! digits found in num must be used.
!
! The program returns the minimum possible sum of new1 and new2.
!
! Example 1:
! Input: num = 2932
! Output: 52
! Explanation: Some possible pairs [new1, new2] are [29, 23], [223, 9], etc.
! The minimum sum can be obtained by the pair [29, 23]: 29 + 23 = 52.
!
! Example 2:
! Input: num = 4009
! Output: 13
! Explanation: Some possible pairs [new1, new2] are [0, 49], [490, 0], etc.
! The minimum sum can be obtained by the pair [4, 9]: 4 + 9 = 13.
!
! Constraints:
! 1000 <= num <= 9999
!--------------------------------------------------------------------------------

program min_sum_of_new1_and_new2
    implicit none

    integer :: num, new1, new2, i, j, k, l, min_sum
    character(len=4) :: num_str

    ! Read the input number
    read(*,*) num

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

    ! Initialize the minimum sum to a large value
    min_sum = huge(min_sum)

    ! Iterate over all possible pairs of new1 and new2
    do i = 0, 9
        do j = 0, 9
            do k = 0, 9
                do l = 0, 9
                    ! Check if the current pair satisfies the constraints
                    if (i*1000 + j*100 + k*10 + l == num) then
                        ! Calculate the sum of new1 and new2
                        new1 = i*1000 + j*100 + k*10 + l
                        new2 = i*1000 + j*100 + k*10 + l
                        min_sum = min(min_sum, new1 + new2)
                    end if
                end do
            end do
        end do
    end do

    ! Print the minimum sum
    write(*,*) min_sum

end program min_sum_of_new1_and_new2
🌐 Data from online sources 
def min_operations(grid, x):
    min_element = min(min(row) for row in grid)
    min_ops = float('inf')

    base = min_element
    while True:
        operations = 0
        impossible = False
        for row in grid:
            if impossible:
                break
            for cell in row:
                diff = abs(cell - base)
                if diff % x != 0:
                    impossible = True
                    break
                operations += diff // x
        if impossible:
            break
        min_ops = min(min_ops, operations)
        base -= 1

    return -1 if min_ops == float('inf') else min_ops
  • Find the minimum element in the grid
  • Initialize the minimum operations to inf
  • Start with base equal to the minimum element, and decrement by 1 for each iteration
  • For each possible base, iterate over every element in the grid and calculate the absolute difference between the current element and base
  • If the difference can't be evenly divided by x, mark it as impossible and break the loop
  • Otherwise, add the number of operations required (difference / x) to obtain a uni-value grid
  • Update the minimum operations with the minimum of the current minimum and the calculated operations
  • Return -1 if the minimum operations remain inf, otherwise return the minimum operations found
🌐 Data from online sources 
#include <vector>
#include <climits>
#include <cmath>

int min_operations(std::vector<std::vector<int>>& grid, int x) {
    int min_elem = INT_MAX;
    for (const auto& row : grid) {
        for (int cell : row) {
            min_elem = std::min(min_elem, cell);
        }
    }

    int min_operations = INT_MAX;
    for (int base = min_elem;; --base) {
        int operations = 0;
        bool impossible = false;
        for (const auto& row : grid) {
            if (impossible) break;
            for (int cell : row) {
                int diff = std::abs(cell - base);
                if (diff % x != 0) {
                    impossible = true;
                    break;
                }
                operations += diff / x;
            }
        }
        if (impossible) break;
        min_operations = std::min(min_operations, operations);
    }

    return min_operations == INT_MAX ? -1 : min_operations;
}
  • Find the minimum element in the grid
  • Initialize the minimum operations to inf
  • Start with base equal to the minimum element, and decrement by 1 for each iteration
  • For each possible base, iterate over every element in the grid and calculate the absolute difference between the current element and base
  • If the difference can't be evenly divided by x, mark it as impossible and break the loop
  • Otherwise, add the number of operations required (difference / x) to obtain a uni-value grid
  • Update the minimum operations with the minimum of the current minimum and the calculated operations
  • Return -1 if the minimum operations remain inf, otherwise return the minimum operations found