CODEWITHSUNDEEP
algorithmmathadditionsubtraction
user2856199
user2856199

Reputation: 51

How to find the largest sum and smallest positive difference?

Using the numbers 9, 8, 7, 6, 5, and 4 once each, find the following:

a) The largest possible sum

Is there more than on solution that gives the largest possible sum? How do you know it's the largest possible sum?

b) The smallest possible (positive) difference

Is there more than one solution? How do you know it's the smallest possible difference?

The numbers must be 3 digits. For example, 965 + 784 or 879 - 654

Upvotes: 5

Views: 12915

Answers (3)

Bas Swinckels
Bas Swinckels

Reputation: 18488

Since you are asking for algorithms, here is a brute force solution in python:

In [1]: from itertools import permutations
In [2]: def gen_pairs():
   ...:     for p in permutations('987654'):
   ...:         yield int(''.join(p[:3])), int(''.join(p[3:]))
In [3]: '%i = %i + %i' % max((a+b, a, b) for a,b in gen_pairs())
Out[3]: '1839 = 975 + 864'
In [4]: '%i = %i - %i' % min((a-b, a, b) for a,b in gen_pairs() if a>b)
Out[4]: '47 = 745 - 698'

This just gives you the minimum and maximum values. To check for uniqueness:

In [4]: [(a,b) for (a,b) in gen_pairs() if a+b == 1839]
Out[4]: 
[(975, 864),
 (974, 865),
 (965, 874),
 (964, 875),
 (875, 964),
 (874, 965),
 (865, 974),
 (864, 975)]

Note that these are just 4 solutions if you do not count the swapped answers.

In [5]: [(a,b) for (a,b) in gen_pairs() if a-b == 47]
Out[6]: [(745, 698)]

So the difference has a unique solution.

I think it is more elegant to solve this problem by logical reasoning, as shown by the others. This just proves that they were right.

Upvotes: 1

Spektre
Spektre

Reputation: 51845

To be sure try all combinations and remember the best solution. but when you smart then you can avoid it by:

  1. max sum is 975 + 864 = 1839

    • or any combination that evenly distribute bigger numbers to higher digit positions
    • just like Shashank Gupta wrote in a comment

  2. the min positive difference is similar 745 - 698 = 47

    • the second number (without first digit) must be as big as possible
    • the first number (without first digit) must be as small as possible
    • the first digits must differ only by 1
    • after some thinking you should come to the same result

Upvotes: 1

mjb4
mjb4

Reputation: 987

Hmm interesting

Difference:

If you always take tupels (a_1,b_1),(a_2,b_2),(a_3,b_3) for a_1a_2a_3-b_1b_2b_3, the difference is:

100*(a_1-b_1)+10*(a_2-b_2)+(a_1-b_1)

So for the smallest difference I guess this should be fullfilled: -(a_2-b_2) > -(a_3-b_3) > (a_1-b_1):

(a_2-b_2) = 4-9 = -5 = d_2
(a_3-b_3) = 5-8 = -3 = d_3
(a_1-b_1) = 7-6 =  1 = d_1

giving you 745-698 = 47 which is the only smallest because in all other variants d_2 will be bigger or d_3 will be bigger or even d_1. Also its unique (so just one solution) because it's asked after the positive difference, so you cannot switch the numbers.

Sum:

So for the sum we got:

100*(a_1+b_1) + 10*(a_2+b_2) + (a_2+b_2)

so now: (a_1+b_1)>(a_2+b_2)>(a_3+b_3):

a_1+b_1 = 8+9 = 17
a_2+b_2 = 7+6 = 13
a_3+b_3 = 4+5 = 9

so it's 964+875 = 975+864 = 1839, it's not unique, but still the biggest. For you can change b_i and a_i you have 2^3 possiblities to build this sum.

Upvotes: 3

Related Questions