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[0]." : ".$result[1]."\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[0]." : ".$result[1]."\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[0]." : ".$result[1]."\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;
}