Pair Sums Facebook

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);