Given a positive integer num, split it into two non-negative integers num1 and num2 such that:
num1 and num2 is a permutation of num.
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:
num does not contain any leading zeros.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 thatnum1is 24 andnum2is 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 thatnum1is 68 andnum2is 7, which would give an optimal sum of 75.
Constraints:
10 <= num <= 109Problem Overview: You receive an integer num. Rearrange its digits to form two new integers such that their sum is as small as possible. Each digit must be used exactly once, and leading zeros are allowed.
Approach 1: Brute Force Digit Partitioning (O(n!))
The naive idea is to generate every permutation of the digits and split them into two numbers in all possible ways. For each configuration, compute the sum and track the minimum. This guarantees the optimal result but quickly becomes infeasible because permutations grow factorially with the number of digits. Even for 10 digits, the search space is massive. This approach mainly helps understand the problem structure but is never practical for real inputs.
Approach 2: Greedy Approach with Sorting (O(n log n))
The optimal observation comes from how place values affect the final sum. Smaller digits should appear in lower place values across both numbers. Start by extracting all digits from num, then sort them in ascending order using a sorting algorithm. Build two numbers by distributing digits alternately: append the smallest digit to the first number, the next to the second number, then repeat.
This greedy distribution keeps both numbers balanced in length and ensures that small digits occupy the most significant positions. If one number becomes significantly longer than the other, its place values grow and increase the sum. Alternating digits avoids that imbalance while preserving the smallest possible leading digits. The approach relies on simple arithmetic operations and sequential iteration over the sorted digit list.
From an algorithm perspective, this combines greedy reasoning with math operations on digits. Sorting dominates the runtime, giving a time complexity of O(n log n), where n is the number of digits. Only a few variables are used to construct the numbers, so the space complexity is O(1) ignoring the digit list.
Recommended for interviews: The greedy sorting approach is the expected solution. Interviewers want to see the insight that distributing the smallest digits across both numbers minimizes the total sum. Mentioning the brute force idea shows you considered the search space, but implementing the greedy strategy demonstrates algorithmic intuition and efficiency.
In this approach, the digits of the number are sorted in ascending order. By alternating assignment of these sorted digits to two different numbers, num1 and num2, we can ensure that they have minimal possible values, and hence their sum is minimized. This is because smaller digits accumulate towards smaller numbers when sorted in ascending order, leading to a smaller total sum.
The function minSum converts the integer to a string to easily sort the digits. By sorting the digits, the smallest values are handled first. It distributes the sorted digits between two numbers num1 and num2 alternately. This guarantees that both numbers are as small as possible for a minimal sum.
Time Complexity: O(n log n) due to the sorting algorithm.
Space Complexity: O(n) for storing the digits.
First, we use a hash table or array cnt to count the occurrences of each digit in num, and use a variable n to record the number of digits in num.
Next, we enumerate all the digits i in nums, and alternately allocate the digits in cnt to num1 and num2 in ascending order, recording them in an array ans of length 2. Finally, we return the sum of the two numbers in ans.
The time complexity is O(n), and the space complexity is O(C). Where n is the number of digits in num; and C is the number of different digits in num, in this problem, C leq 10.
We can convert num to a string or character array, then sort it, and then alternately allocate the digits in the sorted array to num1 and num2 in ascending order. Finally, we return the sum of num1 and num2.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the number of digits in num.
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) due to the sorting algorithm. |
| Counting + Greedy | — |
| Sorting + Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Digit Permutations | O(n!) | O(n) | Only for conceptual understanding or extremely small digit counts |
| Greedy with Sorting | O(n log n) | O(1) | General case and the standard interview solution |
| Greedy with Counting Sort (Digits 0-9) | O(n) | O(1) | When optimizing further since digits range only from 0 to 9 |
Split With Minimum Sum || Addition Rule || Leetcode-2578 • Aryan Mittal • 1,526 views views
Watch 9 more video solutions →Practice Split With Minimum Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor