# Some Coding Puzzle Exercises For Fun - Part 3 - Has Pair With Sum

This exercise is based on the solution found at Google Life's YouTube channel. Admittedly, I was pulling my hair out for a bit on this one.

The question asks the programmer to find an efficient way to find two numbers in a sequence that add up to a number.

Following along in my mind the solution was similar to what was proposed by the interviewee except instead of using the HASH table I used an associative array. Instead of finding all the compliments until I found one that was missing. It made sense to simply add the compliment as the key in the array and if I found a value plus the compliment. Then I would know I had found the answer.

```<?php

\$result = hasPairWithSum([1,2,4,8,12,15,6,5],20);

if(false === \$result) {
print "No results found \n";
}else{
print \$result." : ".\$result."\n";
}

echo "\n";

/**
* hasPairWithSum
*  [1,2,3,9] ?= 8
*  [1,2,4,4] ?= 8
*  @param array
*  @param integer
*
*  @return variant  boolean / array
*  */
function hasPairWithSum(\$set,\$sum) {
// initialize an array to compare against that will contain a list of complementary numbers
\$comp = [];
// get the length of our set
\$l = count(\$set);
// loop the set
for(\$i=0; \$i<\$l; \$i++) {
// have i seen this before?
if(isset(\$comp[\$set[\$i]])) {
// if i have seen this number before does its compliment result in our target sum?
if((\$comp[\$set[\$i]] + \$set[\$i]) == \$sum)
return array(\$comp[\$set[\$i]],\$set[\$i]); // yes,...then return that value
}
// add the current test result to our hash set
\$comp[(\$sum - \$set[\$i])] = \$set[\$i];
}
// didn't find it...?

return false;
}```

Once I found my answer I began adding larger numbers to search for in larger sets by passing some random logic before running the function:

```<?php
\$set = array();

\$sum = floor(rand(1000,10000));

\$set_length = 20000;

\$set_lengths = array();

for(\$i=0; \$i<\$set_length; \$i++) {
\$set[] = floor(rand(1,\$set_length));
}

\$result = hasPairWithSum(\$set,\$sum);

print "sum = ".\$sum."\n";

if(false === \$result) {
print "No results found \n";
}else{
print \$result." : ".\$result."\n";
}

echo "\n";
```

Eventually I hit an out of memory error. To fix this issue I began dropping parts of the set that were no longer necessary by adding this to the loop:

```// have i seen this before?
if(isset(\$comp[\$set[\$i]])) {
// if i have seen this number before does its compliment result in our target sum?
if((\$comp[\$set[\$i]] + \$set[\$i]) == \$sum) {
return array(\$comp[\$set[\$i]],\$set[\$i]); // yes,...then return that value
}else{
// we don't need this anymore, so get rid of it
unset(\$comp[\$set[\$i]]);
}
}```

By doing this I was able to find numbers up to a million with a set length of up to two million...(Maybe more I just haven't pushed it).

The program only takes a few seconds to run.

I think I will build a version to chunk out the task to multiple computers. That should be interesting.

Meanwhile here is the final test code:

```<?php
\$set = array();

\$sum = floor(rand(1000,1000000));

\$set_length = 2000000;

\$set_lengths = array();

for(\$i=0; \$i<\$set_length; \$i++) {
\$set[] = floor(rand(1,\$set_length));
}

\$result = hasPairWithSum(\$set,\$sum);

print "sum = ".\$sum."\n";

if(false === \$result) {
print "No results found \n";
}else{
print \$result." : ".\$result."\n";
}

echo "\n";

/**
* hasPairWithSum
*  [1,2,3,9] ?= 8
*  [1,2,4,4] ?= 8
*  @param array
*  @param integer
*
*  @return variant  boolean / array
*  */
function hasPairWithSum(\$set,\$sum) {
// initialize an array to compare against that will contain a list of complimentary numbers
\$comp = [];
// get the length of our set
\$l = count(\$set);
// loop the set
for(\$i=0; \$i<\$l; \$i++) {
// have i seen this before?
if(isset(\$comp[\$set[\$i]])) {
// if i have seen this number before does its compliment result in our target sum?
if((\$comp[\$set[\$i]] + \$set[\$i]) == \$sum) {
return array(\$comp[\$set[\$i]],\$set[\$i]); // yes,...then return that value
}else{
// we don't need this anymore, so get rid of it
unset(\$comp[\$set[\$i]]);
}
}
// add the current test result to our hash set
\$comp[(\$sum - \$set[\$i])] = \$set[\$i];
}

// didn't find it...?
return false;
}
```

Tags
Category