We have got 3 distinct number, A < B < C.
Let's imagine that the minimum difference Z = (C - B) goes between numbers A and B, closer to B, so new sequence will be A < Z < B < C. And the next minimum difference Y = (B - Z), goes between A and Z, closer to Z, A < Y < Z < B < C and so on.
You see Y + Z = B, Z + B = C, the next number in the sequence (in order from left to right) is equal to the sum of current and previous members (looks like Fibonacci numbers).
Now try to find the sequence with described property.

Look at the example: 1 4 6 10 16 26 ... We can continue this sequence until the last two members will be 519390993822245170 and 840392281454979346. Their sum is more than 10^18. It takes only 83 iterations to build this sequence.

The test case would be: 1 519390993822245170 840392281454979346

So, in the worst case, the number of iteration N < 100.

The naive algorithm, when we just put the minimum diff to the array and sort it again will work. The time complexity will be O(N^2 log N).

Edited by author 01.10.2019 14:24