How to find the minimal possible sum of two distinct elements in an array with PHP

1 Answer

0 votes
/*
    Goal:
    -----
    Find the minimal value of (a[i] + a[j]) for any two distinct elements in an array.

    Efficient Strategy (O(n)):
    --------------------------
    The smallest possible sum of two distinct elements is obtained by:
        - finding the smallest element
        - finding the second smallest element
    Because any other pair must be >= one of these two.

    We scan the array once, keeping track of:
        - min1  = smallest element seen so far
        - min2  = second smallest element seen so far
*/

// A function that computes the minimal sum of two distinct elements.
function minimal_two_sum(array $arr): int {
    // Handle edge case: need at least two elements
    if (count($arr) < 2) {
        throw new InvalidArgumentException("Array must contain at least two elements.");
    }

    // Initialize min1 and min2 to very large values
    $min1 = PHP_INT_MAX;
    $min2 = PHP_INT_MAX;

    // Single pass through the array
    foreach ($arr as $x) {
        if ($x < $min1) {
            // x becomes the new smallest; old min1 becomes min2
            $min2 = $min1;
            $min1 = $x;
        } elseif ($x < $min2) {
            // x is not the smallest, but smaller than the second smallest
            $min2 = $x;
        }
    }

    // The minimal sum of two distinct elements
    return $min1 + $min2;
}

$arr = [7, -3, 10, 1, 5, 2, 4];

try {
    $result = minimal_two_sum($arr);
    echo "Minimal sum of two elements: $result\n";
} catch (Exception $e) {
    echo "Error: " . $e->getMessage() . "\n";
}



/*
run:

Minimal sum of two elements: -2

*/

 



answered Jul 21 by avibootz

Related questions

...