Minimum Sum of Four Digit Number After Splitting Digits

Difficulty: Easy | Acceptance: 86.30% | Paid: No Topics: Math, Greedy, Sorting

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, and all digits must be used.

Return the minimum sum of new1 and new2.

Examples
Constraints
Approach 1: Sorting
Approach 2: Counting Sort (Greedy)
Approach 3: Brute Force Permutations

Examples

Example 1:

Input: num = 2932
Output: 52
Explanation: Some possible valid new pairs are [new1, new2]:
- [22, 93] (sum 115)
- [23, 92] (sum 115)
- [22, 39] (sum 61)
- [2, 932] (sum 934)
- [29, 32] (sum 61)
- [293, 2] (sum 295)
- [32, 29] (sum 61)
- [3, 922] (sum 925)
- [39, 22] (sum 61)
- [92, 23] (sum 115)
- [9, 322] (sum 331)
- [932, 2] (sum 934)
The minimum sum obtainable is 52 (new1 = 29, new2 = 23).

Example 2:

Input: num = 4009
Output: 13
Explanation: The minimum sum is obtained by new1 = 4, new2 = 9.

Constraints

1000 <= num <= 9999

Sorting

Intuition To minimize the sum of two numbers formed by a fixed set of digits, the digits in the “tens” place (the most significant positions in this 2-digit context) must be as small as possible.

Steps

Extract the four digits from the number.
Sort the digits in ascending order.
Assign the two smallest digits to the tens places of the two new numbers, and the two largest digits to the units places.
Calculate the sum as (d[0] * 10 + d[2]) + (d[1] * 10 + d[3]).

python

class Solution:\n    def minimumSum(self, num: int) -> int:\n        digits = sorted(str(num))\n        # Smallest two digits go to tens place\n        return (int(digits[0]) + int(digits[1])) * 10 + int(digits[2]) + int(digits[3])

Complexity

Time: O(1) - Sorting 4 digits is constant time.
Space: O(1) - Storing 4 digits requires constant space.
Notes: This is the most idiomatic approach for this specific constraint.

Counting Sort (Greedy)

Intuition Since the digits are only from 0 to 9, we can use a counting array (bucket sort) to find the smallest digits without a general-purpose sort.

Steps

Create an array count of size 10 initialized to 0.
Iterate through the digits of num and increment the corresponding index in count.
Iterate through count to pick the first two non-zero digits (smallest) for the tens place, and the next two for the units place.

python

class Solution:\n    def minimumSum(self, num: int) -> int:\n        count = [0] * 10\n        for _ in range(4):\n            count[num % 10] += 1\n            num //= 10\n        \n        digits = []\n        for i in range(10):\n            while count[i] > 0:\n                digits.append(i)\n                count[i] -= 1\n        \n        return (digits[0] + digits[1]) * 10 + digits[2] + digits[3]

Complexity

Time: O(1) - Iterating over a fixed size array (10).
Space: O(1) - Fixed size auxiliary array.
Notes: Useful if the range of digits is small but the number of digits is large.

Brute Force Permutations

Intuition Since there are only 4 digits, there are only 4! = 24 possible permutations. We can generate all permutations, split them into two numbers, and track the minimum sum.

Steps

Generate all permutations of the 4 digits.
For each permutation, form two numbers using the first two and last two digits.
Update the global minimum sum.

python

import itertools\n\nclass Solution:\n    def minimumSum(self, num: int) -> int:\n        digits = list(str(num))\n        min_sum = float('inf')\n        \n        for p in itertools.permutations(digits):\n            n1 = int(p[0] + p[1])\n            n2 = int(p[2] + p[3])\n            min_sum = min(min_sum, n1 + n2)\n            \n        return min_sum

Complexity

Time: O(1) - 4! is a constant (24).
Space: O(1) - Recursion depth is constant (4).
Notes: Conceptually simple but overkill for this problem; demonstrates the brute force pattern.