Categories

Pair SumsGiven a list of n integers arr[0..(n-1)], determine the number of different pairs of elements within it which sum to k.If an integer appears in the list multiple times, each copy is considered to be different; that is, two pairs are considered different if one pair includes at least one array index which the other doesn’t, even if they include the same values.

### Signature

int numberOfWays(int[] arr, int k)

### Input

n is in the range [1, 100,000]. Each value arr[i] is in the range [1, 1,000,000,000]. k is in the range [1, 1,000,000,000].

### Output

Return the number of different pairs of elements which sum to k.

### Example 1

n = 5 k = 6 arr = [1, 2, 3, 4, 3] output = 2The valid pairs are 2+4 and 3+3.

### Example 2

n = 5 k = 6 arr = [1, 5, 3, 3, 3] output = 4There’s one valid pair 1+5, and three different valid pairs 3+3 (the 3rd and 4th elements, 3rd and 5th elements, and 4th and 5th elements).

``````
class Solution {

public function __construct(){

}

public function numberOfWays(array \$arr, int \$k) : int {
sort(\$arr); # [1,3,3,3,5]
\$sortedArr = \$arr;

\$p1PrevValue = null;
\$p1Index = 0;
\$p2Index = count(\$sortedArr) - 1; #\$p2Index 4
\$p2Value = \$sortedArr[\$p2Index]; #\$p2Value 5
\$prevP1 = null;
\$countOfWays = 0;

#traverse array
#\$p1Index 0
#\$p2Index 4

while (\$p1Index < \$p2Index) {
\$p1Value = \$sortedArr[\$p1Index]; # 1;3,3
\$p2Value = \$sortedArr[\$p2Index]; # 3;3,3

if(\$p1Value + \$p2Value === \$k) {
\$countOfWays++; #1;2;3
if(\$p1Value === \$p1PrevValue) {
\$countOfWays++; #4
}
\$p1PrevValue = \$p1Value; #1;3
\$p1Index++;# 1;2,3
}

if(\$p1Value + \$p2Value > \$k) {
\$p2Index--; #3
}

if(\$p1Value + \$p2Value < \$k) {
\$p1Index++;
}
}
return \$countOfWays;

}
}

\$solution = new Solution();
\$k = 6;
\$arr = [1,5,3,3,3];

\$countOfWays = \$solution->numberOfWays(\$arr, \$k);

var_dump(\$countOfWays);`````` 