Scale Engineer

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
MathGreedy
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 <= 109

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:

import java.util.*; class Solution {    long minSum = Long.MAX_VALUE;     public int splitNum(int num) {        String s = Integer.toString(num);        List<Character> digits = new ArrayList<>();        for (char c : s.toCharArray()) {            digits.add(c);        }                // Start the recursive partitioning from the first digit.        generatePartitions(0, digits, new ArrayList<>(), new ArrayList<>());        return (int) minSum;    }     private void generatePartitions(int index, List<Character> allDigits, List<Character> list1, List<Character> list2) {        // Base case: all digits have been assigned.        if (index == allDigits.size()) {            // Ensure both numbers are non-empty as per the problem's implicit split.            if (!list1.isEmpty() && !list2.isEmpty()) {                long num1 = buildSmallestNumber(list1);                long num2 = buildSmallestNumber(list2);                minSum = Math.min(minSum, num1 + num2);            }            return;        }         char currentDigit = allDigits.get(index);         // Option 1: Add the current digit to the first number's list.        list1.add(currentDigit);        generatePartitions(index + 1, allDigits, list1, list2);        list1.remove(list1.size() - 1); // Backtrack to explore other possibilities.         // Option 2: Add the current digit to the second number's list.        list2.add(currentDigit);        generatePartitions(index + 1, allDigits, list1, list2);        list2.remove(list2.size() - 1); // Backtrack.    }     // Helper function to build the smallest number from a list of digits.    private long buildSmallestNumber(List<Character> digitList) {        Collections.sort(digitList);        StringBuilder sb = new StringBuilder();        for (char c : digitList) {            sb.append(c);        }        return Long.parseLong(sb.toString());    }}

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.

Solutions

class Solution {public  int splitNum(int num) {    int[] cnt = new int[10];    int n = 0;    for (; num > 0; num /= 10) {      ++cnt[num % 10];      ++n;    }    int[] ans = new int[2];    for (int i = 0, j = 0; i < n; ++i) {      while (cnt[j] == 0) {        ++j;      }      --cnt[j];      ans[i & 1] = ans[i & 1] * 10 + j;    }    return ans[0] + ans[1];  }}

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 →

Next problem