Split With Minimum Sum

Easy

#2358Time: O(2^k * k log k), where `k` is the number of digits in `num`. For each of the `2^k` ways to partition the digits, we sort the two resulting sub-lists. Since `k <= 10`, this is acceptable.Space: O(k) for the recursion depth and to store the lists of digits, where `k` is the number of digits.

Patterns

Math Greedy

Algorithms

Sorting

Prompt

Given a positive integer num, split it into two non-negative integers num1 and num2 such that:

The concatenation of num1 and num2 is a permutation of num.
- In other words, the sum of the number of occurrences of each digit in 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:

It is guaranteed that num does not contain any leading zeros.
The order of occurrence of the digits in num1 and num2 may differ from the order of occurrence of num.

Example 1:

num1

Example 2:

num1

Constraints:

10 <= num <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach systematically explores every possible way to divide the digits of the input number num into two separate groups. For each possible division (or partition), it constructs the two smallest possible numbers, num1 and num2, by arranging the digits in each group in ascending order. It then calculates their sum and keeps track of the minimum sum found across all partitions. While exhaustive and guaranteed to be correct, this method is computationally more intensive than the optimal greedy solution.

Algorithm

1. Extract the digits of the input num into a list.
1. Implement a recursive function generatePartitions that takes the current digit's index and the lists for num1 and num2.
1. In the recursive function, for each digit, explore two branches: adding it to list1 or adding it to list2.
1. The base case for the recursion is when all digits have been assigned. At this point, check if both lists are non-empty.
1. If they are, build the smallest possible numbers from list1 and list2 by sorting their digits and concatenating them.
1. Calculate the sum of these two numbers and update a global minimum sum.
1. After the recursion completes, the global minimum sum is the result.

Walkthrough

The core idea is to treat the problem as finding the best partition of a set of digits. We can use a recursive backtracking algorithm to generate all possible partitions.

For an input number like 4325, the digits are {4, 3, 2, 5}. The algorithm will explore partitions like:

{4} and {3, 2, 5} -> num1=4, num2=235, sum=239
{4, 3} and {2, 5} -> num1=34, num2=25, sum=59
... and so on for all 2^(k-1) - 1 non-trivial partitions.

For each partition, we form the smallest numbers possible. If a partition for num1 is {5, 2}, the smallest number we can form is 25. This is done by sorting the digits within each partition. The algorithm maintains a global minimum, updating it whenever a smaller sum is found.

Here is a code snippet demonstrating the recursive partitioning:

1import java.util.*;2 3class Solution {4    long minSum = Long.MAX_VALUE;5 6    public int splitNum(int num) {7        String s = Integer.toString(num);8        List<Character> digits = new ArrayList<>();9        for (char c : s.toCharArray()) {10            digits.add(c);11        }12        13        // Start the recursive partitioning from the first digit.14        generatePartitions(0, digits, new ArrayList<>(), new ArrayList<>());15        return (int) minSum;16    }17 18    private void generatePartitions(int index, List<Character> allDigits, List<Character> list1, List<Character> list2) {19        // Base case: all digits have been assigned.20        if (index == allDigits.size()) {21            // Ensure both numbers are non-empty as per the problem's implicit split.22            if (!list1.isEmpty() && !list2.isEmpty()) {23                long num1 = buildSmallestNumber(list1);24                long num2 = buildSmallestNumber(list2);25                minSum = Math.min(minSum, num1 + num2);26            }27            return;28        }29 30        char currentDigit = allDigits.get(index);31 32        // Option 1: Add the current digit to the first number's list.33        list1.add(currentDigit);34        generatePartitions(index + 1, allDigits, list1, list2);35        list1.remove(list1.size() - 1); // Backtrack to explore other possibilities.36 37        // Option 2: Add the current digit to the second number's list.38        list2.add(currentDigit);39        generatePartitions(index + 1, allDigits, list1, list2);40        list2.remove(list2.size() - 1); // Backtrack.41    }42 43    // Helper function to build the smallest number from a list of digits.44    private long buildSmallestNumber(List<Character> digitList) {45        Collections.sort(digitList);46        StringBuilder sb = new StringBuilder();47        for (char c : digitList) {48            sb.append(c);49        }50        return Long.parseLong(sb.toString());51    }52}

Complexity

Time

O(2^k * k log k), where `k` is the number of digits in `num`. For each of the `2^k` ways to partition the digits, we sort the two resulting sub-lists. Since `k <= 10`, this is acceptable.

Space

O(k) for the recursion depth and to store the lists of digits, where `k` is the number of digits.

Trade-offs

Pros

It is a correct approach as it exhaustively checks all valid splits of the digits.
It serves as a good baseline to verify the correctness of more optimized solutions.

Cons

The time complexity is exponential, making it inefficient for larger numbers of digits (though feasible for this problem's constraints).
The implementation is significantly more complex than the greedy approach due to recursion and backtracking.

This is the most efficient and elegant solution. The core insight is that to minimize the sum num1 + num2, we should construct num1 and num2 to be as small as possible. A number's magnitude is primarily determined by its most significant digits and its length. By sorting all available digits and then distributing them one by one, alternating between num1 and num2, we achieve two things:

The smallest digits (d1, d2) are placed in the most significant positions of num1 and num2.
The lengths of num1 and num2 are kept as balanced as possible (differing by at most one). This greedy strategy correctly yields the minimum possible sum.

Algorithm

1. Convert the input integer num to a string, then to a character array.
1. Sort the character array in ascending order.
1. Initialize two string builders, s1 and s2.
1. Loop through the sorted character array from i = 0 to length - 1.
1. If i is an even index, append the digit digits[i] to s1.
1. If i is an odd index, append the digit digits[i] to s2.
1. After the loop, convert s1 and s2 to integers.
1. Return the sum of the two integers.

Walkthrough

Let's walk through an example: num = 4325.

Extract and Sort Digits: The digits are 4, 3, 2, 5. Sorting them gives 2, 3, 4, 5.
Distribute Alternately: We build two new numbers, num1 and num2.
- The first smallest digit, 2, goes to num1. (num1 = "2")
- The second smallest digit, 3, goes to num2. (num2 = "3")
- The third smallest digit, 4, goes to num1. (num1 = "24")
- The fourth smallest digit, 5, goes to num2. (num2 = "35")
Calculate Sum: We have num1 = 24 and num2 = 35. Their sum is 24 + 35 = 59.

This process guarantees that the smallest digits contribute to the higher place values (tens, hundreds, etc.), thus minimizing the overall sum. The implementation is straightforward.

Here is the Java code for this approach:

1import java.util.Arrays;2 3class Solution {4    public int splitNum(int num) {5        // Convert the number to a character array to easily access and sort digits.6        char[] digits = Integer.toString(num).toCharArray();7        8        // Sort the digits in ascending order.9        Arrays.sort(digits);10        11        // Initialize two string builders to construct the two new numbers.12        StringBuilder num1Str = new StringBuilder();13        StringBuilder num2Str = new StringBuilder();14        15        // Iterate through the sorted digits and distribute them alternately.16        for (int i = 0; i < digits.length; i++) {17            if (i % 2 == 0) {18                // Even-indexed digits (0, 2, ...) go to the first number.19                num1Str.append(digits[i]);20            } else {21                // Odd-indexed digits (1, 3, ...) go to the second number.22                num2Str.append(digits[i]);23            }24        }25        26        // Convert the resulting strings to integers.27        int num1 = Integer.parseInt(num1Str.toString());28        int num2 = Integer.parseInt(num2Str.toString());29        30        // Return the sum.31        return num1 + num2;32    }33}

Complexity

Time

O(k log k), where `k` is the number of digits in `num`. The dominant operation is sorting the `k` digits. Since `k` is small (at most 10), this is very fast.

Space

O(k) to store the character array for the digits, where `k` is the number of digits.

Trade-offs

Pros

Extremely efficient with a near-linear time complexity.
Simple and concise to implement.
Directly solves the problem without unnecessary exploration of non-optimal solutions.

Cons

The correctness of the greedy choice is not immediately obvious and relies on the insight about minimizing numbers by placing small digits in high-value places.

Solutions

Solution

1class Solution {2public3  int splitNum(int num) {4    int[] cnt = new int[10];5    int n = 0;6    for (; num > 0; num /= 10) {7      ++cnt[num % 10];8      ++n;9    }10    int[] ans = new int[2];11    for (int i = 0, j = 0; i < n; ++i) {12      while (cnt[j] == 0) {13        ++j;14      }15      --cnt[j];16      ans[i & 1] = ans[i & 1] * 10 + j;17    }18    return ans[0] + ans[1];19  }20}

1class Solution:2    def splitNum(self, num: int) -> int: cnt = Counter() n = 0 while num: cnt[num % 10] += 1 num //= 10 n += 1 ans = [0] * 2 j = 0 for i in range(n): while cnt[j] == 0: j += 1 cnt[j] -= 1 ans[i & 1] = ans[i & 1] * 10 + j return sum(ans)

1class Solution {2public:3  int splitNum(int num) {4    int cnt[10]{};5    int n = 0;6    for (; num; num /= 10) {7      ++cnt[num % 10];8      ++n;9    }10    int ans[2]{};11    for (int i = 0, j = 0; i < n; ++i) {12      while (cnt[j] == 0) {13        ++j;14      }15      --cnt[j];16      ans[i & 1] = ans[i & 1] * 10 + j;17    }18    return ans[0] + ans[1];19  }20};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem