Algorithm - Smallest subtraction

Question

We are given list/array (We can use both) of integers
In one move we are able to subtract two of them and put in the list/array
What's the lowest number (or the same numbers) ( > 0 ) we can get doing this operation

f.e we have 6 4 2
First move Take 6 and 4, We get 2 and 2, so anwser is 2

1 7 5
Take 7 and 5, we get 2 and 1, then we get 1

8 20 4 15
Take 20 and 15, we get 8 5 4, take 8 and 5, we get 4 and 3 then we get 1

I can do this in time T(n) = n^n, by comparing everything or sorting every single turn, how we may do this much faster?

Answer 1

Having worked on similar problems, I'm convinced there is no greedy algorithm that can guarantee an optimal result. However, it may not be necessary to look at every single combination of two numbers in every step.

Looking at a few examples, it's obvious that the first number you use should always be the largest one. For lists of 3 or 4 elements, subtracting the second-largest number is always the optimal choice. However, for lists of 5 elements or more, there seems to be no general rule.

10,4,3,2,1  ->  6,3,2,1  ->  3,2,1  ->  1,1  ->  1  (largest minus 2nd-largest: 10-6=4)
10,4,3,2,1  ->  9,4,3,2  ->  5,3,2  ->  2,2  ->  2  (largest minus smallest: 10-1=9)

 9,8,7,6,5  ->  1,7,6,5  ->  1,1,5  ->  1,4  ->  3  (largest minus 2nd-largest: 9-8=1)
 9,8,7,6,5  ->  4,8,7,6  ->  4,1,6  ->  2,1  ->  1  (largest minus smallest: 9-5=4)

I tested an algorithm which tries both the smallest and the second-largest number for each step (resulting in 2ⁿ recursions), but found an example where this doesn't work: 99,78,68,56,52,4,3.

The best solution found by using only smallest or second-largest is 6:

99 78 68 56 52  4  3
96 78 68 56 52  4
92 78 68 56 52
40 78 68 56
40 10    56
   10    16
          6

The best solution found by brute-forcing all options is 1:

99 78 68 56 52  4  3
31 78    56 52  4  3
31 26    56     4  3
   26    25     4  3
    1           4  3
    1           1

If you use the largest number as the only optimisation, this would lead to the following algorithm:

• Find the largest number
• Iterate over every other number, subtract it from the largest number, and recurse

This would have a lower time complexity than trying every combination of two numbers, or sorting after every step.