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

.

## Top comments (0)