Question 40080 in PHP Question posted in
Official manual can be found here.

return the unique pairs of integers from a an array that add up to a specific sum – PHP

I am writing a function that takes in an array of integers and returns the number of unique pairs of integers that add up to a specific sum. For example, given the array [2, 4, 6, 2, 8, 4, 7, 2, 5, 9] and a sum of 10, the function should return 2 + the pairs number[].

function countPairs($arr, $sum) {
  $pairCount = 0;
  $pairs = [];

  for ($i = 0; $i < count($arr); $i++) {
    for ($j = $i + 1; $j < count($arr); $j++) {
      if ($arr[$i] + $arr[$j] == $sum) {
        $pairCount++;
        $pairs[] = [$arr[$i], $arr[$j]];
      }
    }
  }

  return ['pairCount' => $pairCount, 'pairs' => $pairs];
}

this is what I got so far. it works but it doesn’t check whether a pair has already been counted or not, which can result in duplicates. what should do ?

Tags:

3

Answers


  1. 0

    One solution is combine the values together and make them the key. Then just check to see if the array is in the pairs array. I also sorted the values so that 8,2 and 2,8 will be the same.

    function countPairs($arr, $sum) {
  $pairCount = 0;
  $pairs = [];

  for ($i = 0; $i < count($arr); $i++) {
    for ($j = $i + 1; $j < count($arr); $j++) {
      if ($arr[$i] + $arr[$j] == $sum) {
        
        $pair = [$arr[$i], $arr[$j]];
        asort($pair);
        $key = implode(".",$pair);
        
        if(in_array($pair,$pairs) == false){
            $pairs[$key] = $pair;
            $pairCount++;
        }
      }
    }
  }

  return ['pairCount' => $pairCount, 'pairs' => $pairs];
}
    Login or Signup to reply.
  2. 0

    This should so the trick:

    if (!in_array([$arr[$i], $arr[$j]], $pairs) && !in_array([$arr[$j], $arr[$i]], $pairs)) {}

    It checks if the current pair of values has already been counted and stored in the $pairs array. If the pair is not in the array yet, it is added to the $pairs array along with the number of unique pairs, $pairCount.

    function countPairs($arr, $sum) {
  $pairCount = 0;
  $pairs = [];

  
  for ($i = 0; $i < count($arr); $i++) {
    for ($j = $i + 1; $j < count($arr); $j++) {
      if ($arr[$i] + $arr[$j] == $sum) {
        // Check if the pair has already been counted
        if (!in_array([$arr[$i], $arr[$j]], $pairs) && !in_array([$arr[$j], $arr[$i]], $pairs)) {
          $pairCount++;
          $pairs[] = [$arr[$i], $arr[$j]];
        }
      }
    }
  }

  return ['pairCount' => $pairCount, 'pairs' => $pairs];
}

$result = countPairs([2, 4, 6, 2, 8, 4, 7, 2, 5, 9], 10);

echo "Number of unique pairs: " . $result['pairCount'] . "n";
echo "Pairs:n";
foreach ($result['pairs'] as $pair) {
  echo "  [" . $pair[0] . ", " . $pair[1] . "]n";
}
    Login or Signup to reply.
  3. 0

    It’s far more simple to filter duplicates from the array first, rather than trying to figure out if your result has already been seen.

    Then you can also sort the input and then quit early if you’re touching values that are too large.

    Lastly, finding duplicates and counting the result are two separate operations which don’t necessarily need to be coupled like this.

    function findPairs($arr, $sum) {
    $arr = array_unique($arr);
    sort($arr);
    
    $pairs = [];
    for ($i = 0; $i < count($arr); $i++) {
        for ($j = $i + 1; $j < count($arr); $j++) {
            if ($arr[$i] + $arr[$j] == $sum) {
                $pairs[] = [$arr[$i], $arr[$j]];
                echo "!";
                break;
            } else if ($arr[$i] + $arr[$j] > $sum) {
                echo 'X';
                break;
            }
            echo '.';
        }
        echo PHP_EOL;
    }
    
    return $pairs;
}

$arr = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,1,2,3,4,5];
$pairs = findPairs($arr, 15);
$count = count($pairs);

var_dump(json_encode($pairs), $count);

    Output:

    ............!
..........!
........!
......!
....!
..!
!
X
X
X
X
X
X
X
X
X
X
X
X

string(48) "[[1,14],[2,13],[3,12],[4,11],[5,10],[6,9],[7,8]]"
int(7)

    You could even go a step further and do a binary search on the array for $sum - $arr[$i] instead of looping through the entire sub-array in the inner loop.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search