Using PHP i want to find 2 numbers whose sum is in the array

userYmew 0
Viewed 44

I want to Find 2 numbers whose sum is in the array.

$arr = [1,2,5,3]

output should be 3 and 5

2+3=5 and 1+2=3

below is the code which i have tried.

$input = array(1,2,5,3); 
$length = count($input) - 1;
$count = 0;

for ($i = 0; $i <= $length; $i++) {
    for ($j = $i + 1; $j <= $length; $j++) {
        if ($input[$i] + $input[$j] == 0) {
            $count++;
        }
    }
}

echo $count;
php
2 Answers

You're almost there. You're missing an in_array() check:

$matches = [];
for ($i = 0; $i <= $length; $i++) {
    for ($j = $i + 1; $j <= $length; $j++) {
        $sum = $input[$i] + $input[$j];
        if (in_array(sum, $input)) {
            $matches[] = $sum;
        }
    }
}

Please note that this logic will become very slow very fast if you increase the size of $input. Every N items extra will result in N*N extra iterations.

Bonustip: A foreach makes this easier to read:

$matches = [];
foreach( $input as $outerValue ){
    foreach( $input as $innerValue ){
        $sum = $outerValue + $innerValue;
        if (in_array($sum, $input)) {
            $matches[] = $sum;
        }
    }
}

I'm on a little roll: Based on a hunch, this might be faster for larger sets as it performs way less in_array():

$sums = [];
foreach( $input as $outerValue ){
    foreach( $input as $innerValue ){
        $sums[$outerValue + $innerValue] = 1; // use key to avoid duplicates
    }
}
$sums = array_keys($sums);
$matches = array_intersect(array_unique($input), $sums);

For giggles I benchmarked the options:

1. double for + in_array: https://3v4l.org/FHZ7v/perf
PHP     time    mem (mib)
8.2r    0.068   19.45
8.1     0.074   19.68
8.0     0.073   18.83
7.4     0.077   18.41

2. double foreach + in_array: https://3v4l.org/uV5Xq/perf
PHP     time    mem (mib)
8.2r    0.095   19.59   
8.1     0.095   19.64   
8.0     0.093   18.89   
7.4     0.094   18.40   

3. double foreach + intersect: https://3v4l.org/ncWDk/perf
PHP     time    mem (mib)
8.2r    1.998   19.88
8.1     1.989   22.58
8.0     1.988   21.82
7.4     error

My solution wasnt fast at all. Every day you learn. I'm sure this is improvable, but not today ^_^

usermrza0

The solution below, searches for a all the sums starting from each number seperately. You can search for larger sums, by increasing $numbers_of_sum.

    $initial_array = array(1,2,5,3);
    $numbers_of_sum = 2;

    search_for_sum($initial_array, $initial_array, 1, $numbers_of_sum); // recursive call

    function search_for_sum( $initial_array, $sums_so_far, $counter, $stop_counter ){
        foreach($sums_so_far as $sum_number){
            $new_sums = array();
            foreach($initial_array as $number){
                $new_sums[] = $sum_number + $number;
            }

            foreach($new_sums as $sum){
                if(in_array($sum, $initial_array))
                    echo $sum.' is a sum of numbers in the array.<br>';
            }

            if(($counter+1)!=$stop_counter)
                search_for_sum($initial_array, $new_sums, ($counter++), $stop_counter); // recursive call
        }
    }

I hope it helps.

D. Dimopoulos0
Related