1 #!/bin/env perl

2

3 use strict;

4 use warnings;

5 use Data::Dumper;

6

7 # Problem: given an input array of numbers, and a target value, find two numbers

8 # in the input which sum to the target value. Do so with worst case performance

9 # of O(N).

10

11 # Solution: add the input numbers to a hash as they are read, with the number

12 # as the hash key, and it's index position in the input as the hash value.

13

14 # At each step we can do an O(1) lookup in the hash to see if target - num has

15 # already been added to the hash. If it has, we terminate processing and print

16 # the two numbers (along with their indices). Otherwise we add num to the hash

17 # and loop back to read the next input number.

18

19 # Usage: Pass the target value as a command line option, and the number array as

20 # values on stdin, one item per line.

21

22 my $target = $ARGV[0];

23 my $lookfor;

24 my $num;

25 my $i = 0;

26 my %h;

27 while (<STDIN>) {

28 $num = $_;

29 chomp($num);

30 $lookfor = $target - $num;

31 if ( exists $h{$lookfor} ) {

32 print "$num $lookfor (indices $i, ".$h{$lookfor}.")\n";

33 exit(0);

34 }

35 $h{$num} = $i;

36 $i++;

37 }

38 exit(1);

39