1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ We don't solve competitive programming problems here. I would recommend another platform such as codeforces for that. $\endgroup$ – Marcelo Fornet Oct 8 at 23:34
  • $\begingroup$ 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. $\endgroup$ – Marcelo Fornet Oct 8 at 23:36
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.