# Day 18 - Max Number of K-Sum Pairs

You are given an integer array `nums` and an integer `k`.

In one operation, you can pick two numbers from the array whose sum equals `k` and remove them from the array.

Return the maximum number of operations you can perform on the array.

Example 1:

``````Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.
``````

Example 2:

``````Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.
``````

Constraints:

• `1 <= nums.length <= 105`
• `1 <= nums[i] <= 109`
• `1 <= k <= 109`

## Tests

``````import pytest
from .Day18_MaxNumberOfKSumPairs import Solution

s = Solution()

@pytest.mark.parametrize(
"nums,k,expected",
[
([1, 2, 3, 4], 5, 2),
([3, 1, 3, 4, 3], 6, 1),
([3, 5, 1, 5], 2, 0),
([4, 4, 1, 3, 1, 3, 2, 2, 5, 5, 1, 5, 2, 1, 2, 3, 5, 4], 2, 2),
],
)
def test_max_operations(nums, k, expected):
assert s.maxOperations(nums, k) == expected
``````

## Solution

``````from typing import List
import math

class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
max_ops = 0
counts = {}
for n in nums:
if n in counts:
counts[n] = counts[n] + 1
else:
counts[n] = 1

for n in counts:
diff = k - n
if diff in counts and counts[diff] > 0:
ops = 0
if n == k // 2:
ops = math.floor(counts[n] // 2)
else:
ops = min(counts[n], counts[diff])

max_ops += ops
counts[diff] = counts[diff] - ops
counts[n] = counts[n] - ops

return max_ops
``````

## Analysis  ## Commentary

A fairly easy and quick one today. I could definitely have improved it but it will do.

Runtime is `O(n)`. We got over the list once to insert to a map. Then we go over the map keys and do our calculations. Space is `O(n)` because we created a map to store the counts.

Using a map gives us a very quick way to look up `k - n` for each `n`. If we find a match, we can decrement the counts for each number in the match by `min(counts[n], counts[diff])` and increment the max operations by that number.

The other case we need to think of is where `k - n` is `k / 2`. This will break our implementation so we need to add a check for that case and use `math.floor(counts[n] // 2)`. For example, take `k = 2` and `[1, 1, 1, 1]`. If we used `min(counts[n], counts[diff])` we'd get `4` but the correct answer would be `2` which we do get from `math.floor(counts[n] // 2)`.