Watch 10 video solutions for Split With Minimum Sum, a easy level problem involving Math, Greedy, Sorting. This walkthrough by Aryan Mittal has 1,526 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |