You are given a list of integers. Find the pair of integers whose value is closest among all the pair of integers in this list.
You can sort the integers and then consider all
(N-1) consecutive pairs of integers. One of these pairs is surely the closest. Their difference is the answer.
First, let us consider the complexity of a naive brute force solution.
If we consider each possible pair of integers, we will end up with an
O(N*N) solution - given there are
For a file with
T test cases, the over all complexity is
O(N\*N\*T). This will mean about
250 million calculations. This will be too slow to pass within 3 seconds on the CodeChef servers.
As with any brute force solutions, this solution is doing a lot of extra work. It is considering the difference between several pairs of integers that can be ignored.
Consider the case where the list of integers - we will call it
A - is sorted.
The closest pair of integers is one of the N-1 pairs, which appear consecutively in
A[j] are the closest pair of integers, then
i is equal to
We will use Proof by Contradiction.
Let us assume that the pair of closest integers is
i < (j-1)
k > iand
k <= (j-1)
A[k] - A[i]
A[j] - A[k]on both the sides in
A[j] - A[i]
A[j] - A[k]
A[j] are either a better or an equally good choice for pair of closest integers.
This means, at least one of the assumptions is false.
A[j]are not the closest integers
iis equal to
Now, we just need to sort the numbers efficiently and consider the consecutive pairs in one parse. Sorting can be done in place using the Quick Sort algorithm, which sorts in
O(N log N) time. Quick Sort is available in the standard library in almost all languages.
The rest can be resolved in a single parse. The code will look like
Sort A minval = infinity for i = 1 to N-1, inclusive if minval > A[i] - A[i-1] then minval = A[i] - A[i-1] print minval
Can be found here
Can be found here