# Minimum sum of two numbers formed from digits of two arrays

Given two arrays of digits, both of size $$n$$, $$2 \le n \le 9$$, form two separate numbers $$n_1$$ and $$n_2$$, so the difference $$n_1 - n_2$$ is positive and minimal, if multiple solutions are possible the one with the smallest $$n_1$$ is chosen.

Restrictions:

Time: 0.1 s (brute force ain't gonna do it)

Memory: 2 MB

• We don't solve competitive programming problems here. I would recommend another platform such as codeforces for that. – Marcelo Fornet Oct 8 '19 at 23:34
• What happens if all digits in the first array are lower than all numbers in second array. There is no possible answer in that case. – Marcelo Fornet Oct 8 '19 at 23:36

## 1 Answer

This problem can be solved greedily. First remove all digits that are present in both arrays since they can be used as prefix of the number and we keep difference of high order digits as low as possible. Add them to the numbers from lower digits to higher digits in order to obtain smallest $$n_1$$ at the end. Observation: after this process is done all remaining digits in both arrays are different (but this is not very relevant).

Brute force the next digit of $$n_1$$, there are at most 9 possible digits that can be used for $$n_1$$. Fix a digit $$d$$ not used yet in the first array. Once $$d$$ is fixed as the next digit of $$n_1$$ use the largest digit lower than $$d$$ for $$n_2$$ (if no such digit exists continue with next digit for $$n_1$$).

After we have this prefix for $$n_1$$ and $$n_2$$ we already know that the inequality $$n_1 > n_2$$ holds, whatever order we use for following digits. In order to minimize $$n_1 - n_2$$ we should order remaining digits from first array in such a way that $$n_1$$ is minimized and order remaining digits from second array in such a way that $$n_2$$ is maximized. For the first case we should add remaining digits of $$n_1$$ in non-decreasing order, and for $$n_2$$ in non-increasing order.

Next is the pseudo-code for the explained algorithm. Notice that $$n_1$$ and $$n_2$$ are treated as string, not like numbers, so addition means concatenation. Also, instead of dealing with array of digits as input, convert them to array of frequency, $$F_i(d)$$ denotes how many times digit $$d$$ can be used for number $$n_i$$.

F1 = Frequency of each digit in first array.
F2 = Frequency of each digit in first array.

n1 = ""
n2 = ""

# Remove common digits in both arrays
for d in [0..9]:
while F1[d] > 0 and F2[d] > 0:
n1 += d, n2 += d
F1[d] -= 1, F2[d] -= 1

# Brute force next digit for number n1
for d1 in [1..9]:
# Ignore digit if it is not available
if F1[d1] == 0:
continue

d2 = None

# Iterate backwards and find higher digit available for d2
for d2_it in [d1 - 1..0]:
if F2[d2_it] > 0:
d2 = d2_it
break

# If there is no available next digit for n2 continue
if d2 is None:
continue

tmp_n1 = n1 + d1
tmp_n2 = n2 + d2

# Add next digits greedily
for d in [0..9]:
for i in [0..F1[d]):
tmp_n1 += d

for d in [9..0]:
for i in [0..F2[d]):
tmp_n2 += d

# Check difference of this pair
# and keep better pair accordingly to problem restrictions.
# This function will be called at most 9 times.
report tmp_n1, tmp_n2


Notice that report will be called 0 times in case there is no valid answer.