3
$\begingroup$

You have digits from $0$ to $9$, where you have to use every digit only once.

create 2 numbers from the digits so the difference is minimum.

example : $30568 - 29471 = 1097$

What is the lowest result you can get?

$\endgroup$
  • 1
    $\begingroup$ Problem might be more interesting if you could only use each digit once across both sides of the equation. $\endgroup$ – Colonel Panic Dec 13 '16 at 10:55
  • $\begingroup$ Can the differnce be negative? $\endgroup$ – Oliver Ni Dec 14 '16 at 1:12
  • $\begingroup$ *difference, sorry. $\endgroup$ – Oliver Ni Dec 14 '16 at 1:12
11
$\begingroup$

Minimal value is

$50123-49876 = 247$

Taking "difference" as the unsigned distance between the numbers, rather than $\ (a-b)\ $, this is the minimal difference possible between two numbers which use all 10 digits exactly once between them.   Verified by brute force search.

$\endgroup$
  • $\begingroup$ Yep...this is it. $\endgroup$ – Marius Dec 13 '16 at 8:20
3
$\begingroup$

2 variables: 50123-49876=247.
3 variables: 5071-4982-63=26
4 variables: 987-654-321-0=12
5 variables: |108-26-47-35-9|=9
6 variables: ?
7 variables: 95-67-8-4-3-2-10=1
8 variables: 45-8-7-9-6-3-2-10=0
9 variables: 41-8-7-9-5-3-6-2-0=0
10 variables: No positive difference.

$\endgroup$
  • $\begingroup$ You can get 0 with 8 vars by switching the 6 and 7. $\endgroup$ – EagleV_Attnam Dec 13 '16 at 13:44
  • $\begingroup$ |109-27-48-35-6| = 7 $\endgroup$ – SeanC Dec 13 '16 at 16:14
  • 1
    $\begingroup$ 3 variables are enough: 5013-4987-26=0 $\endgroup$ – Etoplay Dec 14 '16 at 15:43
3
$\begingroup$

The answers already here give the correct answer but don't really explain why it's right, so it seems like it may be worth explaining a bit.

First of all, obviously the numbers must both be 5 digits long because otherwise, even if we allow 0 as a leading digit, the difference is at least 012345-9876=2469, and as we'll see it's easy to do better than that.

Now, the leading digit of the larger number must (by definition) be bigger than the leading digit of the smaller. Clearly we want it to be just 1 bigger. Then, to minimize the difference, we want the remaining digits of the larger number to be as small as possible (i.e., the smallest 4 of the remaining digits, in increasing order) and the remaining digits of the smaller number to be as large as possible (i.e., the largest 4 of the remaining digits, in decreasing order).

And now we make the small part as small as possible and the large part as large as possible by using digits 0123 for the small part and digits 9876 for the large part; so those two leading digits must be 4 and 5.

This gives us 50123 - 49876 = 247.

$\endgroup$
0
$\begingroup$

Minimum: 0 - 987654321 = -987654321

$\endgroup$
  • 4
    $\begingroup$ There is no negative difference. Difference between 2 numbers is |A-B|. so it always a non negative number. $\endgroup$ – Jamal Senjaya Dec 13 '16 at 9:05
0
$\begingroup$

This puzzle reminds me of the puzzles on https://projecteuler.net/ .

Brute force method yields the same answer as @Rubio in less than 20 seconds:

Answer:

50123 - 49876 = 247

Output:


    ===================== 5 =====================
    70143 - 69852 = 291
    70142 - 69853 = 289
    70134 - 69852 = 282
    70132 - 69854 = 278
    70124 - 69853 = 271
    70123 - 69854 = 269
    60134 - 59872 = 262
    60132 - 59874 = 258
    60124 - 59873 = 251
    60123 - 59874 = 249
    50123 - 49876 = 247
    ===================== 4 =====================
    ===================== 3 =====================
    ===================== 2 =====================

Here is the code that produced it:

import sys, itertools, re

def main(argv):
    digits = "0987654321"
    first_num_len = 10
    #curr_best = pow(10, len(digits)+1)
    curr_best = 300

    for first_num_len in xrange(len(digits)/2, 1, -1):
         print "=====================", first_num_len, "====================="
         #split up the digits in every possible way
         list = map("".join, itertools.permutations(digits, first_num_len))
         second_num_len = len(digits) - first_num_len
         for num_str in list:
            # get the balance of digits
            delta_digits = ''
            for ch in digits:
                if not ch in num_str:
                    delta_digits+=ch
            list2 = map("".join, itertools.permutations(delta_digits))

            for num_str2 in list2:
                diff = abs(int(num_str) - int(num_str2))
                if(diff < curr_best):
                    if(int(num_str2) < int(num_str)):
                        print num_str, '-', num_str2, '=', diff
                    else:
                        print num_str2, '-', num_str, '=', diff
                    curr_best = diff

if __name__ == "__main__":
    main(sys.argv)

Hope that helps.

$\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.