# Leetcode 1679: Max Number of K-Sum Pairs

--

In this Leetcode problem, we are given an array `nums`

of integers. In one operation, we can take any pair of integers adding up to `k`

and take it out of the array. We want to know the maximum number of operations that we can do following that rule.

For any number `num`

in `nums`

, it can only be paired with `k — num`

for the sum to be equal to`k`

. Then, for any number `1 ≤ p ≤ k — 1`

, if we have the value `p`

repeated `x`

times in `nums`

, and the value `k — p`

repeated `y`

times, we can form `min(x,y)`

pairs using these 2 values, unless `p`

and `k — p`

are the same.

If `k`

is pair, if the value `k/2`

is repeated `x`

times in `nums`

, we can only make `x/2`

pairs using these values. If we ignore this, and apply the same previous formula, `min(x, x)`

, we will count twice as many pairs as needed.

However, we can notice that if we count the pair `(p, k — p)`

, and later on count the pair `(k — p, p)`

, we also will double the number of operations.

Therefore, in the algorithms, we will count all operations twice, by ignoring the special case of `k/2`

, and by counting the pairs `(p, k - p)`

and `(k — p, p)`

. We will only need to divide the result by 2 at the end.

To solve the problem, we count the number of occurrences of each `1 ≤ p < k`

, in a map `count`

. Then for each `key`

in the map we add `min(count.get(key), count.get(k — key))`

to the final result. As explained before, doing this will exactly double the expected final result.

Here is the full Java solution:

`class Solution {`

public int maxOperations(int[] nums, int k) {

if (k == 1) {

return 0;

}

Map<Integer, Integer> count = new HashMap<>();

int n = nums.length;

for (int i = 0; i < n; i++) {

int v = nums[i];

if (v < k) {

count.put(v, count.getOrDefault(v, 0) + 1);

}

}

int res = 0;

for (int key : count.keySet()) {

res += Math.min(

count.getOrDefault(key, 0),

count.getOrDefault(k - key, 0));

}

return res / 2;

}

}