Finding Quadruples with a Target Sum Using PHP

Finding Quadruples with a Target Sum Using PHP | CodeSignal Learn

Introduction

Hello there! Get ready to explore an intriguing problem involving list manipulation and combinatorial logic using the capabilities of PHP . We will tackle the task of finding combinations in a given list whose sum is equivalent to a specified target value . Let's dive into the realm of PHP and number theory for an engaging journey.

Task Statement

-10^6

Estimating Program Evaluation Time

O(N^4)

Solution Explanation

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

The simplest solution is the brute-force approach that iterates over every quadruple of numbers in the list. This has a complexity of $O(N^4)$ .

If you imagine each PHP operation takes a small amount of time and you have a list of a thousand integers, performing $O(N^4)$ operations may result in a runtime far exceeding acceptable limits, possibly taking several hours. Therefore, this is not optimal.

To reduce the complexity to $O(N^3)$ , you can iterate over only three elements and check if the target - element1 - element2 - element3 exists in the list using an array of seen sums. This optimization reduces the time significantly, but further efficiencies can be achieved.

With a solution complexity of $O(N^2)$ — the one we'll build in this lesson using PHP — the execution time becomes feasible, fitting well within the 3-second boundary.

These estimations highlight why optimized solutions are crucial. Our organized solution with time complexity $O(N^2)$ is efficient even for larger inputs, thanks to PHP's built-in functions for handling arrays effectively.

Solution Building: Step 1

Our initial approach is to set up an empty associative array. This associative array will be used to store sums of all pairs of numbers in the list as keys, with indices of the pair as their corresponding values. PHP <?php function findQuadSum($targetSum, $numbers) {$length = count($numbers); $sumMap = array();} ?>

Solution Building: Step 2

Next, populate the associative array. For every pair of integers in the list, calculate their sum and store it as a key in the array, using the indices of the pair as the values. PHP <?php function findQuadSum($targetSum, $numbers) {$length = count($numbers); $sumMap = array(); for ($i = 0; $i < $length - 1; ++$i) {for ($j = $i + 1; $j < $length; ++$j) {$pairwiseSum = $numbers[$i] + $numbers[$j]; if (!isset($sumMap[$pairwiseSum])) {$sumMap[$pairwiseSum] = array();} $sumMap[$pairwiseSum][] = array($i, $j);}}} ?>

Solution Building: Step 3

Finally, iterate through all pairs and, for each, calculate the difference between the target sum and the pair sum, searching for this difference in the associative array. For successful matches, verify that none of the indices overlap. If a suitable set is found, return the four numbers. If unsuccessful, return an empty array. PHP<?php function findQuadSum($targetSum, $numbers) { $length = count($numbers); $sumMap = array(); // Step 2: Populate the associative array with sums of all pairs for ($i = 0; $i < $length - 1; ++$i) { for ($j = $i + 1; $j < $length; ++$j) { $pairwiseSum = $numbers[$i] + $numbers[$j]; if (!isset($sumMap[$pairwiseSum])) { $sumMap[$pairwiseSum] = array(); } $sumMap[$pairwiseSum][] = array($i, $j); } } // Step 3: Search for the complement pairs foreach ($sumMap as $sum => $pairs1) { $complement = $targetSum - $sum; if (isset($sumMap[$complement])) { $pairs2 = $sumMap[$complement]; foreach ($pairs1 as $pair1) { foreach ($pairs2 as $pair2) { list($a, $b) = $pair1; list($c, $d) = $pair2; // Ensure all indices are distinct if ($a !== $c && $a !== $d && $b !== $c && $b !== $d) { return [$numbers[$a], $numbers[$b], $numbers[$c], $numbers[$d]]; } } } } } return []; } $numbers = [5, 15, 2, 7, 8, 4]; $target = 24; print_r(findQuadSum($target, $numbers)); // Array // ( // [0] => 5 // [1] => 7 // [2] => 8 // [3] => 4 // )