# Count Pairs with Difference

Given a set of integers, count the pairs where the difference equals a given integer `d`

.

Consider the set of integers `1 3 5 2 4`

and `d`

= 2. The count of
pairs is 3 and the pairs are `1, 3`

, `2, 4`

, and `3, 5`

.

**Input.**
The input file consists of one or more cases consisting of a pair of
lines. The first line of each case consists of a pair of integers
separated by a single space: the length `l`

of a subsequent list of
integers and the difference `d`

. The second line of each case
consists of `l`

integers separated by a single space. None of the
integers is repeated in the list. The input file is terminated by an
EOF character. Consider the following example.

**Output.**
The output file consists of the count of pairs for each input
case. The following output corresponds to the previous example input.

# Solution

The proposed solution is `O(n log n)`

.

To count the pairs in `1 3 5 2 4`

that are at difference 2, consider
the sorted set and the three pairs in the set.

To count those pairs, consider each integer `n`

from left to right and
look for `n - d`

to the left of `n`

. For example, consider the way we
find pair `A`

. For the first integer `1`

, there is nothing on the left,
so there is no pair.

For the second integer `2`

, only integer `1`

is to the left. Because
`0`

is not to the left, there is no pair.

For the third integer `3`

, integers `1`

and `2`

are to the
left. Because `1`

is to the left, we find our first pair, which
we tag with label `A`

.

When we look for a corresponding integer to the left, it suffices to
consider the integers between the last integer to the left that we
considered and the current integer (marked with `^`

). For example,
consider the way we find pair `B`

after we found `A`

. We consider the
fourth integer `4`

and we look for `2`

to the left. Because we
already considered `1`

, we look for `2`

between `1`

and `4`

. When we
find `2`

, we stop there and find our second pair `B`

.

Another example that it suffices to consider integers between the last
integer to the left and the current integer is when we find pair `C`

.
In this case, the current integer is `5`

and we look for `3`

between
integers `2`

and `5`

. When we find `3`

we find pair `C`

.

# Ruby implementation

# Want to read more?

I love to explain and answer questions on programming problems. I publish a new programming problem and its solution every month. Did I mention that I love to answer questions?

If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.