https://leetcode.com/problems/max-number-of-k-sum-pairs

The question which is asked: how many pairs can be constructed, such that sum in each pair is equal to k. Imagine, that k = 8 and we have numbers 2, 2, 2, 6, 6, 6, 6, 6, 6. Then we can construct 3 pairs in this case. In general if we have c1 times of number x and c2 times of number k - x, we can construct min(c1, c2) pairs with numbers x, k - x. So, all we need to do is to use Counter(nums) to calculate frequency of each number and then iterate over each number val, try to find number equal to k - val and update ans by min(freq, cnt[k - val]). Note also, that when we do this, we count each pair exaclty 2 times, so we need to divide answer by 2 in the end.

Question: what happens, if k = 8, and we working wigh case 4, 4, 4, 4, 4, 4, 4? Then there can be constructed 7//2 = 3 pairs, but when we count we count it 7 times. However in the end we will divide it by 2 and everything will work fine: because there can be only one number like this: k//2 (if k is odd or if there is no such pairs, everythin will be OK as well)

Complexity: time and space complexity is O(n): we iterate over our number twice: when we build counter, and then when we iterate over counter.

Oneliner from Nyx314:

return (lambda c: sum(min(c[n], c[k-n]) for n in c))(Counter(nums))//2

class Solution:
    def maxOperations(self, nums, k):
        cnt, ans = Counter(nums), 0
        for val in cnt:
            ans += min(cnt[val], cnt[k - val])
        return ans//2

If you like the solution, you can upvote it on leetcode discussion section: Problem 1679