Array sum of pairs
Pairs with sum problem
Given an array of integers A[N]. Find all pairs of integers in the array which sum to a given value (v)
Solution
Let us try to solve this problem using brute force approach
Code for sum of pairs method
Here is the code in Perl
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
# Given value $v = 6; # Given array @A = (1, 2, 3, 4, 5); # First loop goes from 0 to number of elements in the array for ($i = 0; $i <= $#A; $i++) { # Second loop goes from the current # element in the first loop to the # last element because there is no # need to check the elements from # the beginning since they are already # covered for ($j = $i + 1; $j <= $#A; $j++) { # Find pairs sum which equals to v if ($A[$i] + $A[$j] == $v) { print $A[$i] . " + " . $A[$j] . " = $v\n"; } } } |
This is not an efficient solution because of the nested loops. We can do better by using an efficient data structure such as a hash table. Insert all array elements into the hash table then for each element check if the difference between the given value and this array element is found in the hash table. If that is the case then print that pair and delete the difference value from the hash table to prevent printing duplicates.
Fast sum of pairs algorithm
Here is the code in Perl
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 |
# Given value $v = 6; # Given array @A = (1, 5, 3, 5, 4, 2); # Empty hash table %H = (); # Insert all elements of the array # to the hash table. The array element # is the hash key and the hash value is # given some dummy value of 1 foreach $a (@A) { # Insert array element to the hash $H{$a} = 1; # Difference between the given value # and the array element $diff = $v - $a; # Check if the difference in the hash and make # sure we do not print cases like 3 + 3 = 6 if ($H{$diff} == 1 && $diff != $a) { print $diff . " + " . $a . " = $v\n"; $H{$diff} = ""; } } |
If you have comments or feedback, please use the comments section below. Thanks for visiting.