Minimum Sum of Four Digit Number After Splitting Digits

Easy

#1967Time: O(1). The number of digits is fixed at 4. The number of unique permutations of 4 items is at most `4! = 24`. For each permutation, we perform a constant number of splits and calculations. Therefore, the total number of operations is constant and does not depend on the value of `num`.Space: O(1). We need space to store the digits and the permutations. Since the number of digits is fixed at 4, the space required is also constant.

Patterns

Math Greedy

Algorithms

Sorting

Prompt

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.

For example, given 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 <= 9999

Approaches

2 approaches with complexity analysis and trade-offs.

This approach explores all possible ways to arrange the four digits and all possible ways to split them into two numbers. It's a "brute-force" method because it doesn't use any specific insight about the problem structure, instead relying on exhaustive search to find the minimum sum.

Algorithm

Convert the 4-digit number num into a list of its individual digits.
Implement a function to generate all unique permutations of this list of digits.
Initialize a variable minSum to a very large value (e.g., Integer.MAX_VALUE).
Iterate through each unique permutation of the digits.
For each permutation (d1, d2, d3, d4):
- a. Calculate the sum for a 1-digit/3-digit split: sum1 = d1 + (100*d2 + 10*d3 + d4). Update minSum = min(minSum, sum1).
- b. Calculate the sum for a 2-digit/2-digit split: sum2 = (10*d1 + d2) + (10*d3 + d4). Update minSum = min(minSum, sum2).
Return minSum.

Walkthrough

First, we extract the four digits from the input number num. Then, we generate all unique permutations of these four digits. For a number like 2932, the digits are 2, 2, 3, 9, and we would generate all 12 unique orderings. For each permutation, say (d1, d2, d3, d4), we consider all possible ways to split it into two non-empty numbers:

new1 = d1, new2 = 100*d2 + 10*d3 + d4
new1 = 10*d1 + d2, new2 = 10*d3 + d4

We calculate the sum new1 + new2 for each of these cases and keep track of the minimum sum found across all permutations and all splits. After checking everything, the minimum value we've recorded is the answer. Note that a split like (d1d2d3, d4) is covered by symmetry when another permutation is considered.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.HashSet;4import java.util.List;5import java.util.Set;6 7class Solution {8    public int minimumSum(int num) {9        String s = Integer.toString(num);10        List<Integer> digitList = new ArrayList<>();11        for (char c : s.toCharArray()) {12            digitList.add(c - '0');13        }14 15        Set<List<Integer>> permutations = new HashSet<>();16        generatePermutations(digitList, 0, permutations);17 18        int minSum = Integer.MAX_VALUE;19 20        for (List<Integer> p : permutations) {21            // Split 1: 1-digit and 3-digit22            int n1_split1 = p.get(0);23            int n2_split1 = p.get(1) * 100 + p.get(2) * 10 + p.get(3);24            minSum = Math.min(minSum, n1_split1 + n2_split1);25 26            // Split 2: 2-digit and 2-digit27            int n1_split2 = p.get(0) * 10 + p.get(1);28            int n2_split2 = p.get(2) * 10 + p.get(3);29            minSum = Math.min(minSum, n1_split2 + n2_split2);30        }31        return minSum;32    }33 34    private void generatePermutations(List<Integer> arr, int k, Set<List<Integer>> permutations) {35        if (k == arr.size()) {36            permutations.add(new ArrayList<>(arr));37            return;38        }39        for (int i = k; i < arr.size(); i++) {40            Collections.swap(arr, i, k);41            generatePermutations(arr, k + 1, permutations);42            Collections.swap(arr, k, i); // backtrack43        }44    }45}

Complexity

Time

O(1). The number of digits is fixed at 4. The number of unique permutations of 4 items is at most `4! = 24`. For each permutation, we perform a constant number of splits and calculations. Therefore, the total number of operations is constant and does not depend on the value of `num`.

Space

O(1). We need space to store the digits and the permutations. Since the number of digits is fixed at 4, the space required is also constant.

Trade-offs

Pros

Guaranteed to find the correct answer by checking all possibilities.
Conceptually straightforward, as it directly translates the problem of "finding the minimum over all possibilities" into code.

Cons

Highly inefficient in terms of the number of computations performed compared to a more insightful approach.
The implementation is more complex due to the need for a permutation generation algorithm.
Does not scale well if the number of digits were to increase.

A much more efficient approach is based on a greedy strategy. To minimize the sum of two numbers, we should try to make the numbers themselves as small as possible. This means the digits with the highest place value (e.g., the tens place) should be the smallest digits available.

Algorithm

Extract the four digits from the input integer num. This can be done either by converting the number to a string or by using mathematical operations (modulo and division).
Store these four digits in an array.
Sort the array of digits in non-decreasing order. Let the sorted digits be d1, d2, d3, d4.
Construct two new integers, new1 and new2. new1 is formed by d1 and d3 (10*d1 + d3), and new2 is formed by d2 and d4 (10*d2 + d4).
Return the sum new1 + new2.

Walkthrough

The key insight is that to minimize new1 + new2, we should minimize the digits in the higher-value positions. The smallest possible numbers we can form are two-digit numbers, as this avoids using the hundreds or thousands place, which would drastically increase the sum.

So, we should form two 2-digit numbers. Let the four digits of num, sorted in ascending order, be d1, d2, d3, d4.

To minimize the sum, we must assign the two smallest digits, d1 and d2, to the tens places of our new numbers. The two larger digits, d3 and d4, should be assigned to the units places.

We can pair them up in two ways: (10*d1 + d3) + (10*d2 + d4) or (10*d1 + d4) + (10*d2 + d3). Both result in the same sum: 10*(d1 + d2) + (d3 + d4).

The algorithm is therefore: extract digits, sort them, and combine them as described to get the minimum sum.

1import java.util.Arrays;2 3class Solution {4    public int minimumSum(int num) {5        // Create an array to store the four digits6        int[] digits = new int[4];7        int i = 0;8        int temp = num;9        10        // Extract digits using modulo and division11        while (temp > 0) {12            digits[i++] = temp % 10;13            temp /= 10;14        }15        16        // Sort the digits in ascending order17        Arrays.sort(digits);18        19        // Form two new numbers by pairing the smallest digits20        // in the tens places and largest in the units places.21        // new1 = d1*10 + d322        // new2 = d2*10 + d423        int new1 = digits[0] * 10 + digits[2];24        int new2 = digits[1] * 10 + digits[3];25        26        return new1 + new2;27    }28}

Complexity

Time

O(1). Extracting 4 digits is a constant time operation. Sorting a fixed-size array of 4 elements is also constant time. The final calculation is a constant number of arithmetic operations.

Space

O(1). We only need an array of size 4 to store the digits.

Trade-offs

Pros

Extremely efficient, performing a minimal number of operations.
Simple and elegant implementation.
Based on a clear mathematical insight, making it robust.

Cons

Requires the insight that pairing the smallest digits in the most significant positions yields the minimum sum. This might not be immediately obvious.

Solutions

Solution

1class Solution {2public3  int minimumSum(int num) {4    int[] nums = new int[4];5    for (int i = 0; num != 0; ++i) {6      nums[i] = num % 10;7      num /= 10;8    }9    Arrays.sort(nums);10    return 10 * (nums[0] + nums[1]) + nums[2] + nums[3];11  }12}

1class Solution {2public:3  int minimumSum(int num) {4    vector<int> nums;5    while (num) {6      nums.push_back(num % 10);7      num /= 10;8    }9    sort(nums.begin(), nums.end());10    return 10 * (nums[0] + nums[1]) + nums[2] + nums[3];11  }12};

1class Solution:2    def minimumSum(self, num: int) -> int: nums = [] while num: nums . append(num % 10) num //= 10 nums . sort() return 10 * (nums[0] + nums[1]) + nums[2] + nums[3]

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