forked from manwar/perlweeklychallenge-club
/
ch-1.pl
61 lines (50 loc) · 1.32 KB
/
ch-1.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#!/opt/perl/bin/perl
use 5.032;
use strict;
use warnings;
no warnings 'syntax';
use experimental 'signatures';
use experimental 'lexical_subs';
#
# 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.
#
#
# This can be solved trivally by taking the difference of all
# pairs of numbers from @N, and see whether their difference
# equals $A. But that leads to a quadractic algorithm.
#
# But we can do this in linear time. For each element $x in @N,
# check with $A - $x exists in @N. Special care has to be taken
# in case $A - $x == $x: we have to make sure $x then appears
# at least twice in @N.
#
# If we store the elements of @N in a hash, checking whether
# number exists in @N can be done in O (1) expected time.
#
LINE: while (!eof ()) {
#
# Read data:
# odd lines are the numbers in @N
# even lines are the differences ($A).
#
my %data;
$data {$_} ++ for <> =~ /[0-9]+/g;
last if eof ();
chomp (my $diff = <>);
foreach my $number (keys %data) {
my $target = $number - $diff;
if ($data {$target} && ($diff || $data {$number} > 1)) {
say 1;
next LINE;
}
}
say 0;
}
__END__