Subtask 1

For the ~40\%~ subtask, it is possible to iterate over all ~N^2~ pairs of numbers and compare the absolute value of their differences, and print the minimum.

Time Complexity: ~\mathcal O(N^2)~

Subtask 2

For the ~60\%~ subtask, a greedy approach can be used. Sort all the elements, and iterate through each pair of adjacent numbers in the sorted array, and print the minimum absolute value of their difference.

Proof of greedy algorithm:

Let the array ~S = S_1, S_2, \dots, S_N~ be the sorted array. The minimum difference between ~S_i~ and any number is ~\min(S_i - S_{i-1}, S_{i+1} - S_i)~. For the sake of contradiction, assume there exists some ~S_j~, ~j \ne i~, such that ~|S_i - S_j| < \min(S_i - S_{i-1}, S_{i+1} - S_i)~ Thus we have two cases:

Case 1: ~j < i-1~

This implies that ~S_i - S_j < S_i - S_{i-1}~.

~\because S~ is sorted, ~S_j \le S_{i-1}~.

~\therefore S_j = S_{i-1} - x~, for ~x \ge 0~.

Substituting, this gives ~S_i - (S_{i-1} - x) < S_i - S_{i-1}~, which gives:

$$\displaystyle (S_i - S_{i-1}) + x < S_i - S_{i-1}$$ $$\displaystyle x < 0$$

~\because x \ge 0~, this is a contradiction.

Case 2: ~j > i+1~

This implies that ~S_j - S_i < S_{i+1} - S_i~.

~\because S~ is sorted, ~S_j \ge S_{i+1}~.

~\therefore S_j = S_{i+1} + x~, for ~x \ge 0~.

Substituting, this gives ~(S_{i+1} + x) - S_i < S_{i+1} - S_i~, which gives:

$$\displaystyle (S_{i+1} - S_i) + x < S_{i+1} - S_i$$ $$\displaystyle x < 0$$

~\because x \ge 0~, this is a contradiction.

~\therefore~ we have proven that ~S_j~ does not exist.

Time Complexity: ~\mathcal O(N \log N)~