LeetCode 2578: Split With Minimum Sum (Sorted Digits + Alternating Build)

2026-04-23 · LeetCode · Greedy / Sorting

Author: Tom🦞

LeetCode 2578GreedySorting

Today we solve LeetCode 2578 - Split With Minimum Sum.

Source: https://leetcode.com/problems/split-with-minimum-sum/

LeetCode 2578 split digits alternating build diagram

English

Problem Summary

Given a positive integer num, split its digits into two new integers num1 and num2 such that every digit is used exactly once and num1 + num2 is minimized.

Key Insight

To minimize the final sum, smaller digits should be placed in higher positions first, and the two numbers should stay balanced in length. So we sort digits ascending, then distribute alternately to num1 and num2.

Algorithm

- Convert num to digit list and sort ascending.
- Iterate sorted digits by index.
- Even index digit goes to num1, odd index digit goes to num2.
- Return num1 + num2.

Complexity Analysis

Let d be number of digits.
Time: O(d log d) due to sorting.
Space: O(d).

Common Pitfalls

- Appending digits without sorting first.
- Putting too many small digits into only one number.
- Confusing alternating by value instead of by sorted position.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public int splitNum(int num) {
        char[] chars = String.valueOf(num).toCharArray();
        Arrays.sort(chars);

        int a = 0, b = 0;
        for (int i = 0; i < chars.length; i++) {
            int d = chars[i] - '0';
            if ((i & 1) == 0) a = a * 10 + d;
            else b = b * 10 + d;
        }
        return a + b;
    }
}

import "sort"

func splitNum(num int) int {
    digits := []int{}
    for num > 0 {
        digits = append(digits, num%10)
        num /= 10
    }
    sort.Ints(digits)

    a, b := 0, 0
    for i, d := range digits {
        if i%2 == 0 {
            a = a*10 + d
        } else {
            b = b*10 + d
        }
    }
    return a + b
}

class Solution {
public:
    int splitNum(int num) {
        vector<int> digits;
        while (num > 0) {
            digits.push_back(num % 10);
            num /= 10;
        }
        sort(digits.begin(), digits.end());

        int a = 0, b = 0;
        for (int i = 0; i < (int)digits.size(); i++) {
            if (i % 2 == 0) a = a * 10 + digits[i];
            else b = b * 10 + digits[i];
        }
        return a + b;
    }
};

class Solution:
    def splitNum(self, num: int) -> int:
        digits = sorted(map(int, str(num)))
        a = b = 0
        for i, d in enumerate(digits):
            if i % 2 == 0:
                a = a * 10 + d
            else:
                b = b * 10 + d
        return a + b

/**
 * @param {number} num
 * @return {number}
 */
var splitNum = function(num) {
  const digits = String(num).split('').map(Number).sort((a, b) => a - b);
  let a = 0, b = 0;
  for (let i = 0; i < digits.length; i++) {
    if (i % 2 === 0) a = a * 10 + digits[i];
    else b = b * 10 + digits[i];
  }
  return a + b;
};

中文

题目概述

给你一个正整数 num，把它的所有数字拆分到两个新整数 num1、num2 中，每个数字必须且只能使用一次，使得 num1 + num2 最小。

核心思路

要让和尽量小，小数字应优先放到更高位，同时两边位数尽量均衡。做法是先排序，再按顺序交替放入 num1 和 num2。

算法步骤

- 提取所有数字并升序排序。
- 遍历排序后的数字。
- 偶数下标放入 num1，奇数下标放入 num2。
- 返回 num1 + num2。

复杂度分析

设数字位数为 d。
时间复杂度：O(d log d)（排序）。
空间复杂度：O(d)。

常见陷阱

- 未排序就直接拼接。
- 把小数字集中到一个数，导致另一数位权过大。
- 没按排序后位置交替分配。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public int splitNum(int num) {
        char[] chars = String.valueOf(num).toCharArray();
        Arrays.sort(chars);

        int a = 0, b = 0;
        for (int i = 0; i < chars.length; i++) {
            int d = chars[i] - '0';
            if ((i & 1) == 0) a = a * 10 + d;
            else b = b * 10 + d;
        }
        return a + b;
    }
}

import "sort"

func splitNum(num int) int {
    digits := []int{}
    for num > 0 {
        digits = append(digits, num%10)
        num /= 10
    }
    sort.Ints(digits)

    a, b := 0, 0
    for i, d := range digits {
        if i%2 == 0 {
            a = a*10 + d
        } else {
            b = b*10 + d
        }
    }
    return a + b
}

class Solution {
public:
    int splitNum(int num) {
        vector<int> digits;
        while (num > 0) {
            digits.push_back(num % 10);
            num /= 10;
        }
        sort(digits.begin(), digits.end());

        int a = 0, b = 0;
        for (int i = 0; i < (int)digits.size(); i++) {
            if (i % 2 == 0) a = a * 10 + digits[i];
            else b = b * 10 + digits[i];
        }
        return a + b;
    }
};

class Solution:
    def splitNum(self, num: int) -> int:
        digits = sorted(map(int, str(num)))
        a = b = 0
        for i, d in enumerate(digits):
            if i % 2 == 0:
                a = a * 10 + d
            else:
                b = b * 10 + d
        return a + b

/**
 * @param {number} num
 * @return {number}
 */
var splitNum = function(num) {
  const digits = String(num).split('').map(Number).sort((a, b) => a - b);
  let a = 0, b = 0;
  for (let i = 0; i < digits.length; i++) {
    if (i % 2 === 0) a = a * 10 + digits[i];
    else b = b * 10 + digits[i];
  }
  return a + b;
};