# PROBLEM LINK:

Practice

Contest

Video Editorial

# DIFFICULTY

CAKEWALK

# PREREQUISITES

# PROBLEM

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.

# QUICK EXPLANATION

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.

# EXPLANATION

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

**integers.**

`N`

For a file with `T`

test cases, the over all complexity is ** O(N\*N\*T)**. This will mean about

**calculations. This will be too slow to pass within**

`250 million`

**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**.

**Lemma:**

The closest pair of integers is one of the N-1 pairs, which appear consecutively in `A`

Alternately, if ** A[i]** and

**are the closest pair of integers, then**

`A[j]`

`i`

is equal to `j-1`

.**Proof:**

We will use **Proof by Contradiction**.

Let us assume that the pair of closest integers is ** A[i]** and

**and**

`A[j]`

`i < (j-1)`

- Consider
∀`A[k]`

`k > i`

and`k <= (j-1)`

- Since
is sorted,`A`

`A[k]`

`>=`

and`A[i]`

`A[k]`

`<=`

`A[j]`

- From
`(2)`

we get`A[k] - A[i]`

`>=`

`0`

- Adding
on both the sides in`A[j] - A[k]`

`(3)`

we get

`A[j] - A[i]`

`>=`

`A[j] - A[k]`

Hence, ** A[k]** and

**are either a better or an equally good choice for pair of closest integers.**

`A[j]`

This means, at least one of the assumptions is false.

- Either
and`A[i]`

are not the closest integers`A[j]`

- Or,
`i`

is equal to`j-1`

**Approach:**

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

# SETTERS SOLUTION

Can be found here

# TESTERS SOLUTION

Can be found here