Watch 10 video solutions for Minimum Sum of Four Digit Number After Splitting Digits, a easy level problem involving Math, Greedy, Sorting. This walkthrough by Bro Coders has 5,271 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 <= 9999Problem Overview: You are given a four-digit integer num. Split its digits into two new integers such that every digit is used exactly once and the sum of the two numbers is minimized. The order of digits inside each number matters, so placing smaller digits in higher place values reduces the total sum.
Approach 1: Brute Force Combination (O(1) time, O(1) space)
Extract the four digits and generate every possible way to distribute them into two two-digit numbers. For each arrangement, build numbers like 10*a + b and 10*c + d, then compute the total sum. Track the minimum across all permutations. Because there are only four digits, the total permutations are constant (4! possibilities). This approach is straightforward and demonstrates the full search space, but it does unnecessary work compared to the greedy observation.
Approach 2: Sorting and Minimal Pairing (O(d log d) time, O(1) space)
Extract the digits and sort them in ascending order using a sorting algorithm. The key greedy insight: to minimize the final sum, distribute the smallest digits across the highest place values of the two numbers. After sorting d0 ≤ d1 ≤ d2 ≤ d3, construct the numbers as (10*d0 + d2) and (10*d1 + d3). This balances the digits between the tens positions instead of stacking the smallest digits in the same number. The method follows a classic greedy strategy where locally optimal placement (smallest digits in highest weight positions) leads to the globally minimal sum.
Digit extraction itself is simple arithmetic using modulo and division, a common pattern in math-based problems. After sorting, constructing the two numbers and returning their sum is constant work.
Recommended for interviews: Sorting and minimal pairing. Interviewers expect you to notice that smaller digits should occupy the tens positions of both numbers. Brute force proves correctness but the greedy approach demonstrates stronger algorithmic intuition and cleaner implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Combination | O(1) | O(1) | Good for understanding the search space or verifying correctness when digits are very small in count. |
| Sorting and Minimal Pairing (Greedy) | O(d log d) | O(1) | Preferred solution. Uses sorting to place the smallest digits in the highest positional weights to minimize total sum. |