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.
To achieve the minimum sum, sort the digits of the number. This allows us to pair smaller digits together, minimizing the individual numbers formed. By arranging the sorted digits into two numbers with minimal values, we can achieve the smallest sum possible.
For instance, for num = 2932, sorting results in [2, 2, 3, 9]. If we distribute them into [2, 3] and [2, 9], we achieve 23 + 29 = 52, which is the minimum sum.
We first convert the number into a string to easily access its digits. We then sort the string using qsort. After sorting, we construct two numbers by pairing the smallest and second smallest digits to create new1, and the third and largest digits to create new2. This minimizes their sum, achieving the solution.
Time Complexity: O(1), since we are only dealing with four digits and sorting a fixed size array.
Space Complexity: O(1), no additional space other than some variables.
Another approach would be to consider all possible ways to distribute the four digits into two numbers new1 and new2 and calculate their sums. Then select the minimum sum. This method explores all possible combinations.
However, this method is less efficient than sorting because evaluating and summing each combination results in more operations. Sorting ensures better performance and simplicity for this specific problem.
We use a nested loop to iterate over all permutations of the digits, effectively trying every possible split into two numbers. The function computeSum is used to calculate the sum of two formed numbers. Although exhaustive, this ensures finding the minimal sum by brute force.
Time Complexity: O(1), factorial calculations for a small fixed number yield constant operations.
Space Complexity: O(1), since operations are done in-place on an array of constant size.
| Approach | Complexity |
|---|---|
| Sorting and Minimal Pairing | Time Complexity: O(1), since we are only dealing with four digits and sorting a fixed size array. |
| Brute Force Combination | Time Complexity: O(1), factorial calculations for a small fixed number yield constant operations. |
| Default Approach | — |
| 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. |
2160 Minimum Sum of Four Digit Number After Splitting Digits || LeetCode 2160|| Biweekly LeetCode 71 • Bro Coders • 5,271 views views
Watch 9 more video solutions →Practice Minimum Sum of Four Digit Number After Splitting Digits with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor