# Minimum Sum of Four Digit Number After Splitting Digits
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-sum-of-four-digit-number-after-splitting-digits)
Canonical: https://scaleengineer.com/dsa/problems/minimum-sum-of-four-digit-number-after-splitting-digits
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
---
## Problem
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
## Brute-Force with Permutations
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.
**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.
**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.
### Explanation
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:

1.  `new1 = d1`, `new2 = 100*d2 + 10*d3 + d4`
2.  `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.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public int minimumSum(int num) {
        String s = Integer.toString(num);
        List<Integer> digitList = new ArrayList<>();
        for (char c : s.toCharArray()) {
            digitList.add(c - '0');
        }

        Set<List<Integer>> permutations = new HashSet<>();
        generatePermutations(digitList, 0, permutations);

        int minSum = Integer.MAX_VALUE;

        for (List<Integer> p : permutations) {
            // Split 1: 1-digit and 3-digit
            int n1_split1 = p.get(0);
            int n2_split1 = p.get(1) * 100 + p.get(2) * 10 + p.get(3);
            minSum = Math.min(minSum, n1_split1 + n2_split1);

            // Split 2: 2-digit and 2-digit
            int n1_split2 = p.get(0) * 10 + p.get(1);
            int n2_split2 = p.get(2) * 10 + p.get(3);
            minSum = Math.min(minSum, n1_split2 + n2_split2);
        }
        return minSum;
    }

    private void generatePermutations(List<Integer> arr, int k, Set<List<Integer>> permutations) {
        if (k == arr.size()) {
            permutations.add(new ArrayList<>(arr));
            return;
        }
        for (int i = k; i < arr.size(); i++) {
            Collections.swap(arr, i, k);
            generatePermutations(arr, k + 1, permutations);
            Collections.swap(arr, k, i); // backtrack
        }
    }
}
```
### 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`.

## Greedy Approach with Sorting
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public int minimumSum(int num) {
        // Create an array to store the four digits
        int[] digits = new int[4];
        int i = 0;
        int temp = num;
        
        // Extract digits using modulo and division
        while (temp > 0) {
            digits[i++] = temp % 10;
            temp /= 10;
        }
        
        // Sort the digits in ascending order
        Arrays.sort(digits);
        
        // Form two new numbers by pairing the smallest digits
        // in the tens places and largest in the units places.
        // new1 = d1*10 + d3
        // new2 = d2*10 + d4
        int new1 = digits[0] * 10 + digits[2];
        int new2 = digits[1] * 10 + digits[3];
        
        return new1 + new2;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  int minimumSum(int num) {
    int[] nums = new int[4];
    for (int i = 0; num != 0; ++i) {
      nums[i] = num % 10;
      num /= 10;
    }
    Arrays.sort(nums);
    return 10 * (nums[0] + nums[1]) + nums[2] + nums[3];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumSum(int num) {
    vector<int> nums;
    while (num) {
      nums.push_back(num % 10);
      num /= 10;
    }
    sort(nums.begin(), nums.end());
    return 10 * (nums[0] + nums[1]) + nums[2] + nums[3];
  }
};

```

### Python

```python
class Solution:
    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]

```