283. Minimum Sum of Two Numbers Formed From Digits of an Array

Given n single digits (each between 0 and 9), split them into two numbers using every digit exactly once - each number getting at least one digit - so that the sum of the two numbers is as small as possible. Print that minimum sum.

Input: The first line contains an integer n. The second line contains n space-separated single digits, each between 0 and 9. Output: Print a single integer - the minimum possible sum of the two numbers formed from the digits.

2 <= n <= 10^5, 0 <= each digit <= 9

A resulting number that happens to start with a 0 (e.g., digits 0 and 2 giving '02') is simply read as its plain numeric value (2) - no special handling needed, since leading zeros don't change a number's actual value.

Split a set of digits into two numbers (using every digit exactly once) so that their sum is as small as possible. Brute force: Try every possible way of splitting the digits into two groups and every possible arrangement within each group, computing the sum for each - this is combinatorially enormous, completely impractical. Optimised: Since giving the SMALLEST digits to the MOST SIGNIFICANT (leftmost) positions is what minimizes any single number (the same principle behind forming the smallest possible number from a set of digits), splitting the smallest digits evenly between two numbers via alternating assignment from a sorted (or min-heap-based) order directly minimizes their combined sum.

Sort all n digits in ascending order using a comparison sort, then alternately assign digits to the two numbers' most-significant positions first (smallest digit becomes the leading digit of number A, next smallest becomes the leading digit of number B, and so on down to least significant), which keeps both numbers short and minimizes the impact of larger digits by pushing them to less significant places. Sorting first is what makes this simple alternating rule correct: without a sorted order, there'd be no guarantee about which digits are 'small enough' to lead. Time: O(n log n) Space: O(n)

Try every way to partition the digits into two non-empty groups and every ordering of digits within each group to form two numbers, compute their sum for each full assignment, and keep the minimum. This is a correct but exhaustive search over an enormous number of partitions and orderings, almost all of which are far from optimal. Time: O(2^n * n!) worst case Space: O(n)

Since digits only range from 0-9, count the occurrences of each digit value in a fixed 10-bucket array and read them back out in sorted order in linear time, instead of using a general comparison sort. Apply the same alternating most-significant-digit-first assignment as before on this sorted sequence. This keeps the same correctness argument but removes the log n factor entirely by exploiting the bounded digit range. Time: O(n) Space: O(1) extra (fixed 10-bucket counts)

1. Pull digits out SMALLEST-FIRST using a min-heap. 2. Deal them ALTERNATELY between the two numbers, appending each pulled digit to whichever number's turn it currently is - this keeps the most significant (leftmost) positions of both numbers as small as possible. 3. Sum the two resulting numbers.

Time: O(n log n) for sorting the digits (or O(n log n) using a min-heap, equivalent complexity, though a min-heap makes the smallest-first extraction pattern more natural to reason about). Space: O(n), for the two resulting number strings.

n = 2 (the minimum size, one digit per number), digits including zero that create a leading zero in one number (still read as its numeric value), and n = 10^5 for performance.

Be ready to explain why ALTERNATING assignment (not giving all small digits to one number) is the correct strategy - alternating balances the number of digits (and hence the significance/place value) each small digit ends up controlling across both numbers.