LeetCode 2578 - Split With Minimum Sum

The problem asks us to take a positive integer num and split its digits into two non-negative integers num1 and num2 such that the sum num1 + num2 is minimized.

leetcodeeasymathgreedysorting

LeetCode Problem 2578

Difficulty: 🟢 Easy
Topics: Math, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to take a positive integer num and split its digits into two non-negative integers num1 and num2 such that the sum num1 + num2 is minimized. Importantly, the digits of num must be entirely used between num1 and num2, but their order can be rearranged, and leading zeros are allowed in both numbers. The input num is guaranteed to be at least two digits (10 <= num <= 10^9) and will not have leading zeros.

The output is the minimum sum of the two integers formed by splitting and reordering the digits of num. The constraints tell us that the number of digits in num is at most 9 or 10, meaning a solution that examines all permutations could be expensive (up to factorial time), so we need a more efficient method.

Important edge cases include numbers with repeated digits (e.g., num = 1111), numbers with digits that could create a leading zero (e.g., num = 1023), and small numbers (e.g., num = 10).

Approaches

A brute-force approach would involve generating all permutations of the digits of num, then trying every possible way to split each permutation into two numbers, and calculating their sum. We would then return the minimum sum. While this guarantees correctness, the factorial growth in permutations (O(d! * 2^d) where d is the number of digits) makes it infeasible for numbers with more than a few digits.

The key insight for an optimal solution is to minimize the sum by forming the smallest possible numbers from the digits. This can be achieved by sorting the digits and distributing them in an alternating manner to num1 and num2. Assigning the smallest digit to num1, the next smallest to num2, the next to num1, and so on ensures that both numbers grow slowly in magnitude, minimizing their sum. This works because larger digits contribute more when placed in higher positions, so balancing the digits across two numbers reduces the overall sum.

Approach Time Complexity Space Complexity Notes
Brute Force O(d! * 2^d) O(d) Generates all permutations and splits to find minimum sum, infeasible for larger numbers
Optimal O(d log d) O(d) Sort digits and alternately assign to two numbers to minimize sum

Algorithm Walkthrough

  1. Convert the number num to a list of its digits for easy manipulation.
  2. Sort the digits in ascending order. Sorting ensures the smallest digits can be used first to minimize the sum.
  3. Initialize two empty lists (or strings) num1_digits and num2_digits to store digits of num1 and num2.
  4. Iterate over the sorted digits and alternately append each digit to num1_digits and num2_digits. This balances the digits across both numbers, ensuring neither becomes excessively large compared to the other.
  5. Convert num1_digits and num2_digits to integers num1 and num2. Leading zeros are automatically handled by integer conversion.
  6. Return the sum of num1 and num2.

Why it works: By sorting the digits and distributing them alternately, we ensure that the larger digits are balanced across the two numbers, preventing one number from becoming disproportionately large. This guarantees the minimal possible sum because any deviation (placing larger digits unevenly) would increase the sum.

Python Solution

class Solution:
    def splitNum(self, num: int) -> int:
        digits = sorted([int(d) for d in str(num)])
        num1_digits, num2_digits = [], []
        for i, d in enumerate(digits):
            if i % 2 == 0:
                num1_digits.append(str(d))
            else:
                num2_digits.append(str(d))
        num1 = int("".join(num1_digits))
        num2 = int("".join(num2_digits))
        return num1 + num2

The Python implementation first converts the number into a list of digits and sorts them. It then alternates assignment to two lists representing num1 and num2. Finally, the lists are joined into strings and converted to integers, and their sum is returned.

Go Solution

import (
    "sort"
    "strconv"
)

func splitNum(num int) int {
    numStr := strconv.Itoa(num)
    digits := make([]int, len(numStr))
    for i, ch := range numStr {
        digits[i] = int(ch - '0')
    }
    sort.Ints(digits)
    num1Str, num2Str := "", ""
    for i, d := range digits {
        if i%2 == 0 {
            num1Str += strconv.Itoa(d)
        } else {
            num2Str += strconv.Itoa(d)
        }
    }
    num1, _ := strconv.Atoi(num1Str)
    num2, _ := strconv.Atoi(num2Str)
    return num1 + num2
}

In Go, the main differences are handling string-to-int conversion and using slices for the digits. Sorting is done via sort.Ints, and integer conversion is done using strconv.Atoi.

Worked Examples

Example 1: num = 4325

Sorted digits: [2, 3, 4, 5]

Distribution: num1_digits = [2, 4], num2_digits = [3, 5]

Numbers formed: num1 = 24, num2 = 35

Sum: 24 + 35 = 59

Example 2: num = 687

Sorted digits: [6, 7, 8]

Distribution: num1_digits = [6, 8], num2_digits = [7]

Numbers formed: num1 = 68, num2 = 7

Sum: 68 + 7 = 75

Complexity Analysis

Measure Complexity Explanation
Time O(d log d) Sorting the digits dominates, where d is the number of digits
Space O(d) Storing digits in lists for sorting and distribution

The algorithm is efficient because the number of digits d is at most 9, so sorting is trivial, and the subsequent operations are linear in the number of digits.

Test Cases

# Provided examples
assert Solution().splitNum(4325) == 59  # basic example
assert Solution().splitNum(687) == 75   # odd number of digits

# Additional tests
assert Solution().splitNum(10) == 1     # minimal 2-digit number
assert Solution().splitNum(123456789) == 246 + 13578  # larger input
assert Solution().splitNum(1111) == 11 + 11  # repeated digits
assert Solution().splitNum(1023) == 13 + 02  # leading zero handled
Test Why
4325 Basic 4-digit example
687 Odd number of digits
10 Smallest valid input
123456789 Max digits, tests alternating distribution
1111 All digits same, tests repeated digits
1023 Leading zero scenario

Edge Cases

The first important edge case is a number with repeated digits, such as 1111. If the algorithm were naive, it might combine all ones in one number and zero in the other, but the alternating distribution ensures an even split, giving the minimal sum.

The second edge case is a number that includes zeros, e.g., 1023. This could lead to leading zeros in one of the split numbers. Since integer conversion discards leading zeros, the algorithm handles this correctly.

The third edge case is the smallest possible input, 10. Sorting and alternating assignment ensure that num1 = 0 and num2 = 1 yields the minimal sum 1, which demonstrates that the approach generalizes to small numbers.