Given a set of integers, count the pairs where the difference equals a given integer
Consider the set of integers
1 3 5 2 4 and
d = 2. The count of
pairs is 3 and the pairs are
2, 4, and
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
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.
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
n - d to the left of
n. For example, consider the way we
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
2 are to the
1 is to the left, we find our first pair, which
we tag with label
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
4 and we look for
2 to the left. Because we
1, we look for
4. When we
2, we stop there and find our second pair
Another example that it suffices to consider integers between the last
integer to the left and the current integer is when we find pair
In this case, the current integer is
5 and we look for
5. When we find
3 we find pair
Want to read more?
I love to explain and answer questions on programming problems, the kind you find in coding interviews. I publish a new programming problem and its solution every Sunday. Did I mention that I love to answer questions?