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 # Overall performance is O(N) in the worst case, since in that case we must

20 # process each input item exactly once. (For each item, we perform one lookup

21 # into the hash, which adds only a small constant to the running time per

22 # iteration of the loop.)

23

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

25 # values on stdin, one item per line.

26

27 my $target = $ARGV[0];

28 my $lookfor;

29 my $num;

30 my $i = 0;

31 my %h;

32 while (<STDIN>) {

33 $num = $_;

34 chomp($num);

35 $lookfor = $target - $num;

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

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

38 exit(0);

39 }

40 $h{$num} = $i;

41 $i++;

42 }

43 exit(1);

44