# ETOOBUSY ðŸš€ minimal blogging for the impatient

# PWC086 - Pair Difference

**TL;DR**

Here we are with TASK #1 from the Perl Weekly Challenge #086. Enjoy!

# The challenge

You are given an array of integers

`@N`

and an integer`$A`

. Write a script to find find if there exists a pair of elements in the array whose difference is`$A`

. Print`1`

if exists otherwise`0`

.

# The questions

Not many questions on this one, apart the ritual ones on input validation.
It might be interesting to know whether the input list `@N`

is ordered
though, because it might change our approach to the solution.

# The solution

I canâ€™t think of a way in which this puzzle does not have a $O(n^2)$
complexity with respect to the number of elements in array `@N`

. *In
general* each pair of items should be checked against `$A`

.

It can be observed, though, that if the array is sorted e.g. in ascending order, itâ€™s possible to do some pruning. As an example, consider this situation:

```
$A = 7;
@N = (1 2 3 1000 2000 3000 3004 3007 5000 6000);
```

When we start taking the `1`

and check it against the `1000`

(with a
difference of `999`

), itâ€™s clear that any element after that will yield
something bigger. Considering that `999`

is *already* bigger than `7`

, it
makes no sense to seach further for a companion to `1`

and we can proceed
with the following candidate (`2`

in the example). In this specific
arrangement, items `5000`

and `6000`

are never considered actually, because
the search will stop at the `3000`

with `3007`

pair.

Anyway, this still is $O(n^2)$ so, as I was saying at the beginningâ€¦ I canâ€™t think of anything better. Maybe sorting the input array is overkill: it does not make the complexity worse (itâ€™s $O(n \cdot log2(n))$ after all) but knowing if itâ€™s already sortedâ€¦ is worth a question anyway.

Ok so for the general case without sorting this is what I came up with:

```
1 sub pair_difference ($A, @N) {
2 $A = -$A if $A < 0;
3 for my $i (0 .. $#N - 1) {
4 for my $j ($i + 1 .. $#N) {
5 return 1 if abs($N[$i] - $N[$j]) == $A;
6 }
7 }
8 return 0;
9 }
```

Itâ€™s really as simple as this: iterate over all possible *distinct* pairs
(lines 3 and 4 make sure of this), take the absolute value of their
difference, and compare it against the absolute value of the input `$A`

.
Stop as soon as you find a match (line 5 has an immediate `return`

), go on
to the end otherwise.

The full script for playing is the following:

```
#!/usr/bin/env perl
use 5.024;
use warnings;
use experimental qw< postderef signatures >;
no warnings qw< experimental::postderef experimental::signatures >;
sub pair_difference ($A, @N) {
$A = -$A if $A < 0;
for my $i (0 .. $#N - 1) {
for my $j ($i + 1 .. $#N) {
return 1 if abs($N[$i] - $N[$j]) == $A;
}
}
return 0;
}
sub main ($A = 7, @N) { say pair_difference($A, @N) }
main(@ARGV);
```

I knowâ€¦ I should settle with a definitive way of doing these scripts!